Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time

David Eppstein, Maarten Löffler, Darren Strash

The degeneracy of an $n$-vertex graph $G$ is the smallest number $d$ such that every subgraph of $G$ contains a vertex of degree at most $d$. We show that there exists a nearly-opt…