Finding All Cliques of an Undirected Graph [H]

Finding All Cliques of an Undirected Graph [H]

September 1973 | Coen Bron* and Joep Kerbosch†
This paper presents two backtracking algorithms for finding all cliques in an undirected graph. The first algorithm generates cliques in lexicographic order, while the second generates them in an order that minimizes the number of branches traversed. Both algorithms use a branch-and-bound technique to prune branches that cannot lead to a clique. The first algorithm maintains three sets: compsub (the current clique being extended), candidates (points that can be added to compsub), and not (points that have already been used to extend compsub and are now excluded). The algorithm recursively extends compsub by selecting a candidate, adding it to compsub, and then updating the candidates and not sets. The second algorithm selects a candidate from a well-chosen position to minimize the number of repetitions of the extension steps. It also uses a counter to track the number of disconnections for each point in not, allowing it to predict when further extensions will not lead to a clique. The paper also compares the performance of the new algorithms with the Bierstone algorithm on two test cases. The new algorithms perform significantly better than Bierstone, especially for large graphs. The paper also discusses the storage requirements of the algorithms and notes that the new algorithms require less storage than Bierstone. Finally, the paper mentions that Bierstone's algorithm does not report isolated points as cliques, while the new algorithm does. The authors also acknowledge the help of others in preparing the test programs and collecting performance statistics.This paper presents two backtracking algorithms for finding all cliques in an undirected graph. The first algorithm generates cliques in lexicographic order, while the second generates them in an order that minimizes the number of branches traversed. Both algorithms use a branch-and-bound technique to prune branches that cannot lead to a clique. The first algorithm maintains three sets: compsub (the current clique being extended), candidates (points that can be added to compsub), and not (points that have already been used to extend compsub and are now excluded). The algorithm recursively extends compsub by selecting a candidate, adding it to compsub, and then updating the candidates and not sets. The second algorithm selects a candidate from a well-chosen position to minimize the number of repetitions of the extension steps. It also uses a counter to track the number of disconnections for each point in not, allowing it to predict when further extensions will not lead to a clique. The paper also compares the performance of the new algorithms with the Bierstone algorithm on two test cases. The new algorithms perform significantly better than Bierstone, especially for large graphs. The paper also discusses the storage requirements of the algorithms and notes that the new algorithms require less storage than Bierstone. Finally, the paper mentions that Bierstone's algorithm does not report isolated points as cliques, while the new algorithm does. The authors also acknowledge the help of others in preparing the test programs and collecting performance statistics.
Reach us at info@study.space