P254: Enumeration of all pseudo-cliques in a graph

P254: Enumeration of all pseudo-cliques in a graph

Input:

A graph $G = (V, E)$ and a threshold $\theta$.

Output:

All pseudo-cliques in $G$, whose densities are no less than $\theta$.

Complexity:

$O(\Delta |V| + \mathrm{min}\{\Delta^2, |V| + |E|\})$ delay with $O(|V| + |E|)$ space.

Comment:

$\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.

Reference:

[Uno2008a] (Bibtex)