A Worst-Case Analysis of the Sequential Method to List the Minimal Hitting Sets of a Hypergraph

DOI10.1137/060653032zbMATH Open1158.68016OpenAlexW2090382625MaRDI QIDQ3544243FDOQ3544243

Authors: Ken Takata 

Publication date: 5 December 2008

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060653032

Recommendations

• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• Lower bounds for three algorithms for transversal hypergraph generation
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals

zbMATH Keywords

hypergraphlisting algorithmssequential methodminimal hitting setread-once Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65)

Cited In (7)

• Lower bounds for three algorithms for transversal hypergraph generation
• Optimizations for the Boolean approach to computing minimal hitting sets
• Fast algorithms for implication bases and attribute exploration using proper premises
• A new method of computing hitting sets applied to diagnosis generation
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Resolution based algorithms for the transversal hypergraph generation problem
• The minimal hitting set generation problem: algorithms and computation

This page was built for publication: A Worst-Case Analysis of the Sequential Method to List the Minimal Hitting Sets of a Hypergraph

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