P107: Enumeration of all maximum cliques in a circle graph
Input:
A circle graph $G = (V, E)$.
Output:
All maximum cliques in $G$.
Complexity:
$O(1)$ time per maximum clique.
Comment:
A graph is a circle graph if it is the intersection graph of chords in a circle. The definition of a circle graph can be found in Information System on Graph Classes and their Inclusions\footnote{\url{http://www.graphclasses.org/classes/gc\_132.html}}.
P77: Enumeration of all maximum cliques of a circular-arc graph
Input:
A circular-arc graph $G =(V, E)$.
Output:
All maximum cliques of $G$.
Complexity:
$O(|V|^{3.5} + \gamma)$.
Comment:
$\gamma$ is the output size, that is the sum of the all solutions. For a family $A$ of arcs on a circle, a graph $G = (V, E)$ is called the \textit{circular-arc graph} for $A$ if there exists a one-to-one correspondence between $V$ and $A$ such that two vertices in $V$ are adjacent if and only if their corresponding arcs in $A$ intersect.
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.
P21: Enumeration of all maximal cliques in a bipartite graph
Input:
A bipartite graph $G=(V,E)$.
Output:
All maximal bicliques 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.
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.
P232: Enumeration of all $c$-isolated maximal cliques in a graph
Input:
A graph $G = (V, E)$ and an integer $c$.
Output:
All avg-$c$-isolated maximal cliques in $G$.
Complexity:
$O(2^cc^5|E|)$ total time.
Comment:
A vertex set $S \subseteq V$ with $k$ vertices is $c$-isolated if it has less than $ck$ outgoing edges, where an outgoing edge is an edge between a vertex in $S$ and a vertex in $V \setminus S$.
P434: Enumeration of all maximal $c$-isolated cliques in a graph
Input:
A graph $G = (V, E)$ and an integer $c$.
Output:
All maximal $c$-isolated cliques in $G$.
Complexity:
$O(2.89^cc^2|E|)$ total time.
Comment:
A vertex set $S \subseteq V$ with $k$ vertices is $c$-isolated if it has less than $ck$ outgoing edges, where an outgoing edge is an edge between a vertex in $S$ and a vertex in $V \setminus S$.
$\Delta$ is the maximum degree of $G$. The density of a subgraph $G[S]$ induced by $S \subseteq V$ is given by the number of edges over the number of all its vertex pairs.
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.