On the complexity of monotone dualization and generating minimal hypergraph transversals
type: Item
instance of: scholarly article
title: On the complexity of monotone dualization and generating minimal hypergraph transversals
zbMATH Open document ID: 1160.68017
published in: Discrete Applied Mathematics
publication date: 2008-09-10T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 06E30
zbMATH DE Number: 5324127
zbMATH Keywords: dualization
zbMATH Keywords: hypergraph transversals
zbMATH Keywords: generation algorithms
zbMATH Keywords: monotone Boolean functions
zbMATH Keywords: polynomial space
author: Khaled Elbassioni
MaRDI profile type: Publication
full work available at URL: j.dam.2007.05.030
OpenAlex ID: W2005389099
cites work: Q4004178
cites work: Q4099676
cites work: An O(m n) algorithm for regular set-covering problems
cites work: Complexity of identification and dualization of positive Boolean functions
cites work: An inequality for polymatroid functions and its applications.
cites work: LATIN 2004: Theoretical Informatics
cites work: Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
cites work: Dual subimplicants of positive Boolean functions
cites work: Dualization of regular Boolean functions
cites work: Q3804207
cites work: Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
cites work: Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
cites work: Identifying the Minimal Transversals of a Hypergraph and Related Problems
cites work: New results on monotone dualization and generating hypergraph transversals
cites work: New Results on Monotone Dualization and Generating Hypergraph Transversals
cites work: Computational aspects of monotone dualization: a brief survey
cites work: On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
cites work: All maximal independent sets and dynamic dominance for sparse graphs
cites work: On the Complexity of Dualization of Monotone Disjunctive Normal Forms
cites work: How to assign votes in a distributed system
cites work: Q4473243
cites work: Advances in Artificial Intelligence
cites work: Q4386975
cites work: On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
cites work: On generating all maximal independent sets
cites work: The complexity of parallel search
cites work: Q4268444
cites work: Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
cites work: On the Complexity of Some Enumeration Problems for Matroids
cites work: A global parallel algorithm for the hypergraph transversal problem
cites work: Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
cites work: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
cites work: Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
cites work: The Maximum Latency and Identification of Positive Boolean Functions
cites work: A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
cites work: Design by example: An application of Armstrong relations
cites work: NP-completeness: A retrospective
cites work: An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
cites work: Q3997892
cites work: Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
cites work: Almost all monotone Boolean functions are polynomially learnable using membership queries
cites work: Q3026386
DOI: 10.1016/J.DAM.2007.05.030
description: scientific article; zbMATH DE number 5324127