Algorithm 457 Finding All Cliques of an Undirected Graph [H]

Algorithm 457 Finding All Cliques of an Undirected Graph [H]

September 1973 | Coen Bron* and Joep Kerbosch† [Recd. 27 April 1971 and 23 August 1971]
Algorithm 457, presented by Coen Bron and Joep Kerbosch, introduces two backtracking algorithms for finding all maximal complete subgraphs (cliques) in an undirected graph. The first version generates cliques in lexicographic order, while the second version aims to minimize the number of branches by generating larger cliques first and those with a large common intersection. The algorithms use a branch-and-bound technique to prune branches that cannot lead to a clique, enhancing efficiency. The detailed implementation and performance evaluation are discussed, showing that the second version performs well across different graph dimensions and structures, outperforming Bierstone's algorithm in terms of computing time and storage requirements. The paper also includes remarks on other algorithms, such as Algorithm 323 for generating permutations in lexicographic order, Algorithm 408 for sparse matrix operations, and Algorithm 420 for hidden-line plotting, highlighting their improvements and corrections.Algorithm 457, presented by Coen Bron and Joep Kerbosch, introduces two backtracking algorithms for finding all maximal complete subgraphs (cliques) in an undirected graph. The first version generates cliques in lexicographic order, while the second version aims to minimize the number of branches by generating larger cliques first and those with a large common intersection. The algorithms use a branch-and-bound technique to prune branches that cannot lead to a clique, enhancing efficiency. The detailed implementation and performance evaluation are discussed, showing that the second version performs well across different graph dimensions and structures, outperforming Bierstone's algorithm in terms of computing time and storage requirements. The paper also includes remarks on other algorithms, such as Algorithm 323 for generating permutations in lexicographic order, Algorithm 408 for sparse matrix operations, and Algorithm 420 for hidden-line plotting, highlighting their improvements and corrections.
Reach us at info@study.space