Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation

DOI10.1007/978-3-540-74839-7_30zbMath1141.68532OpenAlexW1570878271MaRDI QIDQ3508578

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

Related Items

Computational aspects of monotone dualization: a brief survey

Cites Work

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