P210: Enumeration of all cliques in a graph with degeneracy $d$

P210: Enumeration of all cliques in a graph with degeneracy $d$

Input:

A graph $G = (V, E)$ with degeneracy $d$.

Output:

All cliques in $G$.

Complexity:

$O(d|V|3^{d/3})$ time.

Comment:

They also show the largest possible number of maximal cliques in $G$. The number is $(|V|-d)3^{d/3}$.

Reference:

[Eppstein2010] (Bibtex)