Algorithm 457: finding all cliques of an undirected graph

Coen Bron, Joep Kerbosch · Communications of the ACM · 1973

Summary

Two backtracking algorithms are presented, using a branchand-bound technique [4] to cut off branches that cannot lead to a clique, and generates cliques in a rather unpredictable order in an attempt to minimize the number of branches to be traversed.

Type: article
Published: 1973-09-01
Cited by: 2,609
References: 9
Access: Open access
DOI: https://doi.org/10.1145/362342.362367
OpenAlex: https://openalex.org/W2116007667
Semantic Scholar: https://api.semanticscholar.org/CorpusID:13886709

Keywords

Citation, Graph, Computer science, World Wide Web, Theoretical computer science

References

An Analysis of Some Graph Theoretical Cluster TechniquesJ. Gary Augustson, Jack Minker — 1970
Corrections to Bierstone's Algorithm for Generating CliquesGordon D. Mulligan, Derek G. Corneil — 1972
On cliques in graphsJ. W. Moon, Leo Moser — 1965
Finding cliques in an undirected graphCoen Bron, Jagm Kerbosch, HJ Henk Schell — 1972
Algorithm 202: generation of permutations in lexicographical orderMok-Kong Shen — 1963
The Actual Choice of N and M for Algorithm 202 Generation of Permutations in Lexico- Graphical Order Algorithm 203 Steep1Wen-Tiwa Chu, Donald N Saathoff, J. Wegstein

Cited by

Comparison of Clique-Listing AlgorithmsEric Harley — 2004
Résolution de problèmes combinatoires par des approches fondées sur la notion d'explicationHadrien Cambazard — 2006
Atomic contact vectors in protein‐protein recognitionJulian Mintseris, Zhiping Weng — 2003
Recent advances in chemoinformatics.신석호 — 2007
The pairwise approach to model a large set of disaggregates with common trendsAntoni Espasa, Guillermo Carlomagno — 2014
Data-Driven Visualization and Group Analysis of Multichannel EEG Coherence with Functional UnitsMontserrat Colomer — 2008
Structure-based function prediction: approaches and applications.Pier Federico Gherardini, Manuela Helmer‐Citterich — 2008
Multi-modal Classification in a One-class SettingMatthijs Hovelynck — 2010
Enhance the performance of current scoring functions with the aid of 3D protein-ligand interaction fingerprintsLip Sam Thi, Mohd Noor Mohd Sharif, Amer Nordin Darus — 2017
Graph Alignments: A New Concept to Detect Conserved Regions in Protein Active SitesNils Weskamp, Eyke Hüllermeier, Daniel Kühn — 2004
Scalable Graph Algorithms with Applications in GeneticsYun Zhang — 2008
A Parallel Neural Networks Algorithm for the Clique Partitioning ProblemHaidar Harmanani — 2002
Molecular similarity and xenobiotic metabolismSam Adams — 2010
Clique detection for nondirected graphs: Two new algorithmsLeonhard Gerhards, Wolfgang Lindenberg — 1979
Multivariate Markov networks for fitness modelling in an estimation of distribution algorithmAlexander E. I. Brownlee — 2009
Anytime Algorithms for Mining Groups with Maximum CoverageSatya Gautam Vadlamudi, P. P. Chakrabarti, Sudeshna Sarkar — 2012
Maximum independent set and related problems, with applicationsSergiy Butenko, P. M. Pardalos — 2003
Interpretation of Design Drawings by AnalogyPatrick W. Yaner, Ashok K. Goel — 2006
Fault detection in complex and distributed systemsDejan P. Jovanović — 2014
Computing multifractal spectra via simplicial measuresTomáš Gedeon, Jesse Berwald — 2011

Algorithm 457: finding all cliques of an undirected graph

Summary

Keywords

References

Cited by

Related papers