P26: Enumeration of all independent sets in an input chordal graph

P26: Enumeration of all independent sets in an input chordal graph

Input:

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

Output:

All independent sets in $G$.

Complexity:

$O(1)$ delay and $O(|V|(|V|+|E|))$ time and space for preprocessing.

Comment:

Counting all independent sets in an input chordal graph needs $O(n+m)$ time.

Reference:

[Okamoto2008] (Bibtex)