Exact algorithms for finding minimum transversals in rank-3 hypergraphs
2004 (English)In: Journal of Algorithms, ISSN 0196-6774, Vol. 51, no 2, 107-121 p.Article in journal (Refereed) Published
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.6538n) for a hypergraph with n vertices, and needs polynomial space. The second algorithm uses exponential space and runs in time O(1.6316n).
Place, publisher, year, edition, pages
2004. Vol. 51, no 2, 107-121 p.
Minimum transversal, Hypergraph, 3-Hitting Set, Exact algorithm
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-14395DOI: 10.1016/j.jalgor.2004.01.001OAI: oai:DiVA.org:liu-14395DiVA: diva2:23416