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