P283: Enumeration of all independent sets of size $k$ in a chordal graph

P283: Enumeration of all independent sets of size $k$ in a chordal graph

Input:

A chordal graph $G = (V, E)$ and a positive integer $k$.

Output:

All independent sets of size $k$ in $G$.

Complexity:

Constant time per solution on average after $O((|V| + |E|)|V|^2)$ time for preprocessing.

Comment:

Reference:

[Okamoto2005a] (Bibtex)