Bron–Kerbosch algorithm

In computer science, the Bron–Kerbosch algorithm is an enumeration algorithm for finding maximal cliques in an undirected graph. That is, it lists all subsets of vertices with the two properties that each pair of vertices in one of the listed subsets is connected by an edge, and no listed subset can have any additional vertices added to it while preserving its complete connectivity. The Bron–Kerbosch algorithm was designed by Dutch scientists Coenraad Bron and Joep Kerbosch, who published its description in 1973. Although other algorithms for solving the clique problem have running times that are, in theory, better on inputs that have few maximal independent sets, the Bron–Kerbosch algorithm and subsequent improvements to it are frequently reported as being more efficient in practice than the alternatives. Itby repeatedly selecting the vertex of minimum degree among the remaining vertices. If the order of the vertices  that the Bron–Kerbosch algorithm loops through is a degeneracy ordering, then the set  of candidate vertices in each call (the neighbors of  that are later in the ordering) will be guaranteed to have size at most . The set  of excluded vertices will consist of all earlier neighbors of , and may be much larger than . In recursive calls to the algorithm below the topmost level of the recursion, the pivoting version can still be used.

In pseudocode, the algorithm performs the following steps:

 algorithm BronKerbosch3(G) is
     P = V(G)
     R = X = empty
     for