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

DOI10.1137/060653032zbMath1158.68016OpenAlexW2090382625MaRDI QIDQ3544243

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

hypergraphsequential methodlisting algorithmsminimal hitting setread-once Boolean functions

Mathematics Subject Classification ID

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

Related Items (4)

The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ Fast algorithms for implication bases and attribute exploration using proper premises ⋮ Resolution based algorithms for the transversal hypergraph generation problem ⋮ Lower bounds for three algorithms for transversal hypergraph generation

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