On the complexity of monotone dualization and generating minimal hypergraph transversals
From MaRDI portal
Publication:943847
DOI10.1016/j.dam.2007.05.030zbMath1160.68017OpenAlexW2005389099MaRDI QIDQ943847
Publication date: 10 September 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2007.05.030
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Boolean functions (06E30)
Related Items
The adjacency matrix of a graph as a data table: a geometric perspective ⋮ On Dualization over Distributive Lattices ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ Decision systems in rough set theory: A set operatorial perspective ⋮ A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ A study on monotone self-dual Boolean functions ⋮ Resolution based algorithms for the transversal hypergraph generation problem ⋮ Lower bounds for three algorithms for transversal hypergraph generation ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Design by example: An application of Armstrong relations
- A global parallel algorithm for the hypergraph transversal problem
- Computational aspects of monotone dualization: a brief survey
- Dualization of regular Boolean functions
- An O(m n) algorithm for regular set-covering problems
- The complexity of parallel search
- On generating all maximal independent sets
- An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- An inequality for polymatroid functions and its applications.
- Almost all monotone Boolean functions are polynomially learnable using membership queries
- Monotone Boolean dualization is in co-NP\([\log^{2}n\).]
- Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- Complexity of identification and dualization of positive Boolean functions
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
- New results on monotone dualization and generating hypergraph transversals
- How to assign votes in a distributed system
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
- The Maximum Latency and Identification of Positive Boolean Functions
- A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
- NP-completeness: A retrospective
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Dual subimplicants of positive Boolean functions
- On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
- On the Complexity of Some Enumeration Problems for Matroids
- Advances in Artificial Intelligence
- LATIN 2004: Theoretical Informatics
