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.68104MaRDI 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

dualization; generation algorithms; frequent sets; hypergraph transversals; monotone properties; empty boxes

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic, Unnamed Item, On Quantifying Literals in Boolean Logic and its Applications to Explainable AI, On Tackling Explanation Redundancy in Decision Trees, Enumerating Minimal Transversals of Hypergraphs without Small Holes, Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots, 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, A note on systems with max-min and max-product constraints, Scientific contributions of Leo Khachiyan (a short overview), Combinatorial optimization in system configuration design, Resolution based algorithms for the transversal hypergraph generation problem, Asymptotically optimal dualization algorithms, Efficient algorithms for dualizing large-scale hypergraphs, On the complexity of the dualization problem, The Minimal Hitting Set Generation Problem: Algorithms and Computation, How to Apply SAT-Solving for the Equivalence Test of Monotone Normal Forms, Enumeration of Minimal Dominating Sets and Variants, Towards a Scalable Query Rewriting Algorithm in Presence of Value Constraints

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