P77: Enumeration of all maximum cliques of a circular-arc graph
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.