P366: Enumeration of all maximal independent sets in an interval graph

P366: Enumeration of all maximal independent sets in an interval graph

Input:

An interval graph $G = (V, E)$.

Output:

All maximal independent sets in $G$.

Complexity:

$O(|V|^2 + \beta)$ total time.

Comment:

$\beta$ is the sum of the vertices in all maximal independent sets of $G$.

Reference:

[Leung1984] (Bibtex)