Hypergraph / Transversal (Bibtex)

P302: Enumeration of all minimal transversal of a hypergraph

Input:

A hypergraph $\mathcal{H}$.

Output:

All minimal transversal of $\mathcal{H}$.

Complexity:

$(n + N)^{O(\log n)}$ total time with $O(n \log n)$ words.

Comment:

$n = \sum_{X \in \mathcal{H}}|X|$ and $N$ is the number of solutions.

Reference:

[Tamaki2000] (Bibtex)

P141: Enumeration of all minimal transversal in a hypergraph

Input:

A hypergraph $\mathcal{H}\in A(k, r)$.

Output:

All minimal transversal in $\mathcal{H}$.

Complexity:

$O(n^{k+r+1}|\mathcal{H}^d|^{r+1})$ total time and $O(N^{r+1})$ total space.

Comment:

$A(k, r)$ is the class of hyperedges with $(k, r)$-bounded intersections, i.e. in which the intersection of any $k$ distinct hyperedges has size at most $r$. Minimal transversals of hypergraphs in some restricted classes can be enumerating in polynomial delay and space.

Reference:

[Boros2004] (Bibtex)