P470: Enumeration of all maximal cliques in a graph
P470: Enumeration of all maximal cliques in a graph
Input:
Graph $G = (V, E)$.
Output:
All maximal cliques in $G$.
Complexity:
$\tilde{O}(qd(\Delta + qd))$ delay with $O(q)$ space and $\tilde{O}(|E|)$ preprocessing time, or $\tilde{O}(min\{md, qd\Delta\})$ delay with $O(d)$ space and $\tilde{O}(|E|)$ preprocessing time, where $\Delta$ is the maximum degree, $d$ is the degeneracy, and $q$ is the largest clique size.