P29: Enumeration of all maximal independent sets in a graph
P29: Enumeration of all maximal independent sets in a graph
Input:
A graph $G=(V,E)$.
Output:
All maximal independent sets included in $G$.
Complexity:
$O(n(m+n\log C))=O(n^3)$ delay and exponential space.
Comment:
$C$: total number of maximal independent sets, $n$: total number of vertices, and $m$: total number of edges. Is there no polynomial space and delay algorithm?