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

DOI10.1016/J.DAM.2006.04.012MaRDI QIDQ860396zbMATH OpenOpenAlexFDO

Authors Endre Boros, Khaled Elbassioni, Leonid G. Khachiyan, Vladimir 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

generation algorithmsfrequent setsdualizationhypergraph transversalsmonotone propertiesempty boxes

Mathematics Subject Classification ID

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

Recommendations

• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals
• An Efficient Algorithm for the Transversal Hypergraph Generation
• Lower bounds for three algorithms for transversal hypergraph generation
• scientific article; zbMATH DE number 1670855
• Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation
• Computing and Combinatorics
• Resolution based algorithms for the transversal hypergraph generation problem
• Faster Algorithms to Enumerate Hypergraph Transversals
• Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
• A Lower Bound for the HBC Transversal Hypergraph Generation

Cites work

• scientific article; zbMATH DE number 53984 (Why is no real title available?)
• scientific article; zbMATH DE number 2038737 (Why is no real title available?)
• scientific article; zbMATH DE number 2080472 (Why is no real title available?)
• scientific article; zbMATH DE number 2086380 (Why is no real title available?)
• scientific article; zbMATH DE number 3441892 (Why is no real title available?)
• A new algorithm for the largest empty rectangle problem
• Complexity of identification and dualization of positive Boolean functions
• Computing the Largest Empty Rectangle
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Generating dual-bounded hypergraphs
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Integer Programming and Combinatorial Optimization
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms

Cited in

(38)

• Tropical polar cones, hypergraph transversals, and mean payoff games
• Lower bounds for three algorithms for transversal hypergraph generation
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• Incremental complexity of a bi-objective hypergraph transversal problem
• Towards a Scalable Query Rewriting Algorithm in Presence of Value Constraints
• Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots
• scientific article; zbMATH DE number 1670855 (Why is no real title available?)
• A note on systems with max-min and max-product constraints
• A global parallel algorithm for the hypergraph transversal problem
• A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
• Set covering-based surrogate approach for solving sup-\({\mathcal{T}}\) equation constrained optimization problems
• Efficient algorithms for dualizing large-scale hypergraphs
• Masking patterns in sequences: A new class of motif discovery with don't cares
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
• On Tackling Explanation Redundancy in Decision Trees
• Achieving new upper bounds for the hypergraph duality problem through logic
• On the complexity of the dualization problem
• How to apply SAT-solving for the equivalence test of monotone normal forms
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals
• Combinatorial optimization in system configuration design
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Resolution based algorithms for the transversal hypergraph generation problem
• Efficient algorithms for dualizing large-scale hypergraphs
• Transversal hypergraphs and families of polyhedral cones
• scientific article; zbMATH DE number 1931696 (Why is no real title available?)
• Minimal solutions of fuzzy relation equations via maximal independent elements
• The minimal hitting set generation problem: algorithms and computation
• New theoretical results on the monotone Boolean duality and the monotone Boolean dualization problems
• Enumeration of minimal dominating sets and variants
• Enumerating minimal transversals of hypergraphs without small holes
• scientific article; zbMATH DE number 7310243 (Why is no real title available?)
• Discovery of the \(D\)-basis in binary tables based on hypergraph dualization
• Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation
• Asymptotically optimal dualization algorithms
• Scientific contributions of Leo Khachiyan (a short overview)
• An Efficient Algorithm for the Transversal Hypergraph Generation
• An incremental algorithm for computing the transversal hypergraph
• On quantifying literals in Boolean logic and its applications to explainable AI

This page was built for publication: An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q860396)