An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

DOI10.1016/j.dam.2006.04.012zbMath1110.68104OpenAlexW2012628629MaRDI QIDQ860396

Endre Boros, Khaled M. Elbassioni, Leonid G. Khachiyan, Vladimir A. Gurvich

Publication date: 9 January 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.012

zbMATH Keywords

dualizationgeneration algorithmsfrequent setshypergraph transversalsmonotone propertiesempty boxes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On Tackling Explanation Redundancy in Decision Trees, A note on systems with max-min and max-product constraints, The Minimal Hitting Set Generation Problem: Algorithms and Computation, Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots, Efficient algorithms for dualizing large-scale hypergraphs, Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic, Enumerating Minimal Transversals of Hypergraphs without Small Holes, Scientific contributions of Leo Khachiyan (a short overview), How to Apply SAT-Solving for the Equivalence Test of Monotone Normal Forms, Discovery of the \(D\)-basis in binary tables based on hypergraph dualization, Set covering-based surrogate approach for solving sup-\({\mathcal{T}}\) equation constrained optimization problems, Tropical polar cones, hypergraph transversals, and mean payoff games, Masking patterns in sequences: A new class of motif discovery with don't cares, Enumeration of Minimal Dominating Sets and Variants, Towards a Scalable Query Rewriting Algorithm in Presence of Value Constraints, Resolution based algorithms for the transversal hypergraph generation problem, Combinatorial optimization in system configuration design, On the complexity of the dualization problem, Unnamed Item, On Quantifying Literals in Boolean Logic and its Applications to Explainable AI, Asymptotically optimal dualization algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new algorithm for the largest empty rectangle problem
• 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: Partial and Multiple Transversals of a Hypergraph
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• Computing the Largest Empty Rectangle
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
• Generating dual-bounded hypergraphs
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Integer Programming and Combinatorial Optimization