| Autor: |
Cochefert, Manfred, Couturier, Jean-Francois, Gaspers, Serge, Kratsch, Dieter |
| Rok vydání: |
2015 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
A transversal of a hypergraph is a set of vertices intersecting each hyperedge. We design and analyze new exponential-time algorithms to enumerate all inclusion-minimal transversals of a hypergraph. For each fixed k>2, our algorithms for hypergraphs of rank k, where the rank is the maximum size of a hyperedge, outperform the previous best. This also implies improved upper bounds on the maximum number of minimal transversals in n-vertex hypergraphs of rank k>2. Our main algorithm is a branching algorithm whose running time is analyzed with Measure and Conquer. It enumerates all minimal transversals of hypergraphs of rank 3 on n vertices in time O(1.6755^n). Our algorithm for hypergraphs of rank 4 is based on iterative compression. Our enumeration algorithms improve upon the best known algorithms for counting minimum transversals in hypergraphs of rank k for k>2 and for computing a minimum transversal in hypergraphs of rank k for k>5. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
