P222: Enumeration of all maximal cliques in a graph
P222: Enumeration of all maximal cliques in a graph
Input:
A graph $G = (V, E )$.
Output:
All maximal Cliques in $G$.
Complexity:
$O(\frac{\Delta M_c Tri^2}{P})$ delay and $O(|V| + |E|)$ space.
Comment:
$\Delta$ is the maximum degree in $G$, $M_c$ is the size of the maximum clique in $G$, and $Tri$ is the number of triangles in $G$. This algorithm runs on the computer with $P$ processors.