Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation

DOI10.1007/978-3-540-74839-7_30MaRDI QIDQ3508578zbMATH OpenOpenAlexFDO

Authors Matthias Hagen

Publication date 1 July 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74839-7_30

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Lower bounds for three algorithms for transversal hypergraph generation
• A Lower Bound for the HBC Transversal Hypergraph Generation
• An Efficient Algorithm for the Transversal Hypergraph Generation
• Computing and Combinatorics
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

Cites work

• An Efficient Algorithm for the Transversal Hypergraph Generation
• Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices
• How to assign votes in a distributed system
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• On generating all maximal independent sets
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the complexity of inferring functional dependencies
• On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
• On the frequency of the most frequently occurring variable in dual monotone DNFs
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction

Cited in

(7)

• Lower bounds for three algorithms for transversal hypergraph generation
• An Efficient Algorithm for the Transversal Hypergraph Generation
• A Worst-Case Analysis of the Sequential Method to List the Minimal Hitting Sets of a Hypergraph
• A Lower Bound for the HBC Transversal Hypergraph Generation
• Computing and Combinatorics
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• Computational aspects of monotone dualization: a brief survey

This page was built for publication: Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation

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