P25: Enumeration of all maximal independent sets in a chordal graph

P25: Enumeration of all maximal independent sets in a chordal graph

Input:

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

Output:

All maximal independent sets in $G$.

Complexity:

$O(|V||E|\mu)$ total time.

Comment:

$\mu$ is the number of maximal independent sets of $G$. This algorithm can also enumerate all the maximal cliques.

Reference:

[Tsukiyama1977a] (Bibtex)