# 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)$$.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects) 05C65 Hypergraphs 68Q25 Analysis of algorithms and problem complexity
##### Keywords:
Minimum transversal; Hypergraph; 3-Hitting Set; Exact algorithm
Full Text: