The worst-case time complexity for generating all maximal cliques and computational experiments

We present a depth-first search algorithm for generating all maximal cliques of an undirected graph, in which pruning methods are employed as in the Bron-Kerbosch algorithm. All the maximal cliques generated are output in a tree-like form. Subsequently, we prove that its worst-case time complexity is O(3(n/3)) for an n-vertex graph. This is optimal as a function of it, since there exist up to 3(n/3) maximal cliques in an n-vertex graph. The algorithm is also demonstrated to run very fast in practice by computational experiments. (C) 2006 Elsevier B.V. All rights reserved.