P230: Enumeration of all $c$-isolated pseudo-clique in a graph

P230: Enumeration of all $c$-isolated pseudo-clique in a graph

Input:

A graph $G = (V, E)$ and a positive real number $c$.

Output:

All $c$-isolated $PC(k-\log k, \frac{k}{\log k})$ in $G$.

Complexity:

$O(c^42^{2c}|E|)$ total time.

Comment:

$PC(\alpha, \beta)$ is a induced subgraph of $G$ with an average degree at least $\alpha$ and the minimum degree at least $\beta$.

Reference:

[Ito2009] (Bibtex)