We modify an algorithm of Bron and Kerbosch [1973] for maximal clique enumeration to choose more carefully the order in which the vertices are processed, giving us a fixed-parameter tractable algorithm with running time O(dn3 d/3 ) on graphs with n vertices and degeneracy d. Our time bound matches a worst-case bound of (n − d)3 d/3 on the number of maximal cliques when d is a multiple of 3 and n ≥ d + 3. For graphs with degeneracy d and maximum clique size κ, the algorithm satisfies a time bound of O(d 2 n(d/κ) κ ), and for K h -minor-free graphs we obtain a time bound of n2 O(h log log h) , matching a bound of Fomin et al. [2010] for the number of cliques in these graphs. We implement our algorithm and provide a comparative analysis of it and a different variation of the Bron-Kerbosch algorithm by Tomita et al. [2006] on a large corpus of real-world graphs with low degeneracy. Our algorithm always performs comparably with Tomita et al. on moderately sized graphs, in some cases is much faster, and due to its more space-efficient data structures is capable of being applied to significantly larger graphs.
In practice, algorithms for maximal cliques enumeration or counting can deal with large real-world graphs but hardly scale to very large graphs REF .
Listing All Maximal Cliques in Large Sparse Real-World Graphs
JEAL
Mathematics