P462: Enumerate all minimal dominating sets in a threshold graph.

P462: Enumerate all minimal dominating sets in a threshold graph.

Input:

A threshold graph $G = (V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(|V|^2)$ total time.

Comment:

A threshold graph has exactly $\omega(G)$ minimal dominating sets, where $\omega(G)$ is the size of maximum clique in $G$.

Reference:

[Couturier2013a] (Bibtex)