P20: Enumeration of all maximal cliques in a graph
P20: Enumeration of all maximal cliques in a graph
Input:
A graph $G=(V,E)$.
Output:
All maximal cliques included in $G$.
Complexity:
$O(M(n))$ time delay and $O(n^2)$ space, or $O(\delta^4)$ time delay and $O(n+m)$ space, after $O(nm)$ preprocessing.
Comment:
$M(n)$: the time needed to multiply two $n \times n$ matrices, $\delta$: maximum degree of $G=(V,E)$, $n$: total number of vertices, and $m$: total number of edges.