P27: Enumeration of all maximum independent sets in an input chordal graph

P27: Enumeration of all maximum independent sets in an input chordal graph

Input:

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

Output:

All maximum independent sets in $G$.

Complexity:

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

Comment:

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

Reference:

[Okamoto2008] (Bibtex)