P232: Enumeration of all $c$-isolated maximal cliques in a graph
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$.