P185: Enumeration of all maximal cliques in a connected graph

P185: Enumeration of all maximal cliques in a connected graph

Input:

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

Output:

All maximal cliques in $G$.

Complexity:

$O(\alpha(G)|E|)$ total time and linear space.

Comment:

$\alpha(G)$ is the minimum number of edge-disjoint spanning forests into which $G$ can be decomposed.

Reference:

[Chiba1985] (Bibtex)