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

DOI10.1137/060653032MaRDI QIDQ3544243zbMATHOpenAlexFDO

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

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)

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

Cited in

(7)

• A new method of computing hitting sets applied to diagnosis generation
• Lower bounds for three algorithms for transversal hypergraph generation
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Resolution based algorithms for the transversal hypergraph generation problem
• Fast algorithms for implication bases and attribute exploration using proper premises
• Optimizations for the Boolean approach to computing minimal hitting sets
• 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)