P189: Enumeration of all 2-dominating sets in a tree

P189: Enumeration of all 2-dominating sets in a tree

Input:

A tree $T = (V, E)$.

Output:

All 2-dominating sets of $T$.

Complexity:

$O(1.3248^n)$ total time.

Comment:

If a subset $U\subseteq V$ is a 2-dominating set if every vertex $v \in V \setminus U$ has at least two neighbors in $U$.

Reference:

[Krzywkowski2013] (Bibtex)