We describe an algorithm for finding all maximal cliques in a graph, in time O(dn3d/3) where n is the number of vertices and d is the degeneracy of the graph, a standard measure of its sparsity. This time bound matches the worst-case output size for these parameters. The algorithm modifies the Bron-Kerbosch algorithm for maximal cliques by ordering the vertices by degree in the outer recursive call of the algorithm.
For the journal version, see "Listing all maximal cliques in large sparse real-world graphs in near-optimal time," which combines results from this and a different conference paper.
Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.