zbMATH — the first resource for mathematics

Exact algorithms for finding minimum transversals in rank-3 hypergraphs. (English) Zbl 1091.68083
Summary: We present two algorithms for the problem of finding a minimum transversal in a hypergraph of rank 3, also known as the 3-Hitting Set problem. This problem is a natural extension of the vertex cover problem for ordinary graphs. The first algorithm runs in time \(O(1.6538^n)\) for a hypergraph with \(n\) vertices, and needs polynomial space. The second algorithm uses exponential space and runs in time \(O(1.6316^n)\).

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
05C65 Hypergraphs
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI