P28: Enumeration of all independent sets with $k$ vertices in an input chordal graph

P28: Enumeration of all independent sets with $k$ vertices in an input chordal graph

Input:

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

Output:

All maximum independent sets with $k$ vertices in $G$.

Complexity:

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

Comment:

The number of independent sets with $k$ vertices in an input chordal graph needs $O(k^2(|V|+|E|))$ time.

Reference:

[Okamoto2008] (Bibtex)