Recent from talks
Bron–Kerbosch algorithm
Knowledge base stats:
Talk channels stats:
Members stats:
Bron–Kerbosch algorithm
In computer science, the Bron–Kerbosch algorithm is an enumeration algorithm for finding all 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. It is well-known and widely used in application areas of graph algorithms such as computational chemistry.
A contemporaneous algorithm of Akkoyunlu (1973), although presented in different terms, can be viewed as being the same as the Bron–Kerbosch algorithm, as it generates the same search tree.
The basic form of the Bron–Kerbosch algorithm is a recursive backtracking algorithm that searches for all maximal cliques in a given graph G. More generally, given three disjoint sets of vertices R, P, and X, it finds the maximal cliques that include all of the vertices in R, some of the vertices in P, and none of the vertices in X. In each call to the algorithm, P and X are disjoint sets whose union consists of those vertices that form cliques when added to R. In other words, P ∪ X is the set of vertices which are joined to every element of R. When P and X are both empty there are no further elements that can be added to R, so R is a maximal clique and the algorithm outputs R.
The recursion is initiated by setting R and X to be the empty set and P to be the vertex set of the graph. Within each recursive call, the algorithm considers the vertices in P in turn; if there are no such vertices, it either reports R as a maximal clique (if X is empty), or backtracks. For each vertex v chosen from P, it makes a recursive call in which v is added to R and in which P and X are restricted to the neighbor set N(v) of v, which finds and reports all clique extensions of R that contain v. Then, it moves v from P to X to exclude it from consideration in future cliques and continues with the next vertex in P.
That is, in pseudocode, the algorithm performs the following steps:
The basic form of the algorithm, described above, is inefficient in the case of graphs with many non-maximal cliques: it makes a recursive call for every clique, maximal or not. To save time and allow the algorithm to backtrack more quickly in branches of the search that contain no maximal cliques, Bron and Kerbosch introduced a variant of the algorithm involving a "pivot vertex" u, chosen from P (or more generally, as later investigators realized, from P ⋃ X). Then, neighbors of that pivot element are not recursively tested. Any maximal clique potentially found in tests of neighbors of u would also be found when testing u or one of its non-neighbors, as at least one of these will always be a part of that maximal clique. Otherwise, only neighbors of u would be part of that maximal clique, allowing it to be augmented by adding u to it, which contradicts that clique being maximal. Therefore, only u and its non-neighbors need to be tested as the choices for the vertex v that is added to R in each recursive call to the algorithm. In pseudocode:
If the pivot is chosen to minimize the number of recursive calls made by the algorithm, the savings in running time compared to the non-pivoting version of the algorithm can be significant.
Hub AI
Bron–Kerbosch algorithm AI simulator
(@Bron–Kerbosch algorithm_simulator)
Bron–Kerbosch algorithm
In computer science, the Bron–Kerbosch algorithm is an enumeration algorithm for finding all 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. It is well-known and widely used in application areas of graph algorithms such as computational chemistry.
A contemporaneous algorithm of Akkoyunlu (1973), although presented in different terms, can be viewed as being the same as the Bron–Kerbosch algorithm, as it generates the same search tree.
The basic form of the Bron–Kerbosch algorithm is a recursive backtracking algorithm that searches for all maximal cliques in a given graph G. More generally, given three disjoint sets of vertices R, P, and X, it finds the maximal cliques that include all of the vertices in R, some of the vertices in P, and none of the vertices in X. In each call to the algorithm, P and X are disjoint sets whose union consists of those vertices that form cliques when added to R. In other words, P ∪ X is the set of vertices which are joined to every element of R. When P and X are both empty there are no further elements that can be added to R, so R is a maximal clique and the algorithm outputs R.
The recursion is initiated by setting R and X to be the empty set and P to be the vertex set of the graph. Within each recursive call, the algorithm considers the vertices in P in turn; if there are no such vertices, it either reports R as a maximal clique (if X is empty), or backtracks. For each vertex v chosen from P, it makes a recursive call in which v is added to R and in which P and X are restricted to the neighbor set N(v) of v, which finds and reports all clique extensions of R that contain v. Then, it moves v from P to X to exclude it from consideration in future cliques and continues with the next vertex in P.
That is, in pseudocode, the algorithm performs the following steps:
The basic form of the algorithm, described above, is inefficient in the case of graphs with many non-maximal cliques: it makes a recursive call for every clique, maximal or not. To save time and allow the algorithm to backtrack more quickly in branches of the search that contain no maximal cliques, Bron and Kerbosch introduced a variant of the algorithm involving a "pivot vertex" u, chosen from P (or more generally, as later investigators realized, from P ⋃ X). Then, neighbors of that pivot element are not recursively tested. Any maximal clique potentially found in tests of neighbors of u would also be found when testing u or one of its non-neighbors, as at least one of these will always be a part of that maximal clique. Otherwise, only neighbors of u would be part of that maximal clique, allowing it to be augmented by adding u to it, which contradicts that clique being maximal. Therefore, only u and its non-neighbors need to be tested as the choices for the vertex v that is added to R in each recursive call to the algorithm. In pseudocode:
If the pivot is chosen to minimize the number of recursive calls made by the algorithm, the savings in running time compared to the non-pivoting version of the algorithm can be significant.