An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
From MaRDI portal
Publication:860396
DOI10.1016/J.DAM.2006.04.012zbMATH Open1110.68104OpenAlexW2012628629MaRDI QIDQ860396FDOQ860396
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65)
Cites Work
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Title not available (Why is that?)
- Complexity of identification and dualization of positive Boolean functions
- Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
- Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
- Generating dual-bounded hypergraphs
- Title not available (Why is that?)
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
- Computing the Largest Empty Rectangle
- A new algorithm for the largest empty rectangle problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Integer Programming and Combinatorial Optimization
Cited In (38)
- Tropical polar cones, hypergraph transversals, and mean payoff games
- Lower bounds for three algorithms for transversal hypergraph generation
- Incremental complexity of a bi-objective hypergraph transversal problem
- Dual-bounded generating problems: Weighted transversals of a hypergraph
- Towards a Scalable Query Rewriting Algorithm in Presence of Value Constraints
- Title not available (Why is that?)
- Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots
- 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
- Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
- Masking patterns in sequences: A new class of motif discovery with don't cares
- 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
- An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals
- How to apply SAT-solving for the equivalence test of monotone normal forms
- Combinatorial optimization in system configuration design
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Efficient algorithms for dualizing large-scale hypergraphs
- Resolution based algorithms for the transversal hypergraph generation problem
- Transversal hypergraphs and families of polyhedral cones
- Title not available (Why is that?)
- 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
- Enumerating minimal transversals of hypergraphs without small holes
- Enumeration of minimal dominating sets and variants
- Title not available (Why is that?)
- 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
- An incremental algorithm for computing the transversal hypergraph
- Scientific contributions of Leo Khachiyan (a short overview)
- An Efficient Algorithm for the Transversal Hypergraph Generation
- 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)
