Algorithm 457: finding all cliques of an undirected graph

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithm 457: finding all cliques of an undirected graph

Full text

Pdf (457 KB)

Source

Communications of the ACM archive
Volume 16 , Issue 9 (September 1973) table of contents

Pages: 575 - 577

Year of Publication: 1973

ISSN:0001-0782

Authors

Coen Bron	Technological Univ. Eindhoven, Eindhoven, The Netherlands
Joep Kerbosch	Technological Univ. Eindhoven, Eindhoven, The Netherlands

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 113, Downloads (12 Months): 976, Citation Count: 68

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/362342.362367 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. Gary Augustson , Jack Minker, An Analysis of Some Graph Theoretical Cluster Techniques, Journal of the ACM (JACM), v.17 n.4, p.571-588, Oct. 1970 [doi>10.1145/321607.321608]
	2	Bierstone, E. Unpublished report. U of Toronto.
	3	Bron, C., Kerbosch, J.A.G.M., and Schell, H.J. Finding cliques in an undirected graph. Tech. Rep. Technological U. of Eindhoven, The Netherlands.
	4	Little, John D.C., et al. An algorithm for the traveling salesman problem. Oper. Res. 11 (1963), 972-989.
	5	Moon, J.W., and Moser, L. On cliques in graphs. Israel J. Math. 3 (1965), 23-28.
	6	Gordon D. Mulligan , D. G. Corneil, Corrections to Bierstone's Algorithm for Generating Cliques, Journal of the ACM (JACM), v.19 n.2, p.244-247, April 1972 [doi>10.1145/321694.321698]

CITED BY 68

	Nan Du , Bin Wu , Xin Pei , Bai Wang , Liutong Xu, Community detection in large-scale social networks, Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis, p.16-25, August 12-12, 2007, San Jose, California
	Ranga Vemuri , Srinivas Katkoori , Meenakshi Kaul , Jay Roy, An efficient register optimization algorithm for high-level synthesis from hierarchical behavioral specifications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.189-216, January 2002
	Edoardo Charbon , Enrico Malavasi , Davide Pandini , Alberto Sangiovanni-Vincentelli, Simultaneous placement and module optimization of analog IC's, Proceedings of the 31st annual conference on Design automation, p.31-35, June 06-10, 1994, San Diego, California, United States
	Dong-wan Tcha , Yong-joo Chung , Taek-jin Choi, A new lower bound for the frequency assignment problem, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.34-39, Feb. 1997
	C. J. Tseng , D. P. Siewiorek, Facet: A procedure for the automated synthesis of digital systems, Papers on Twenty-five years of electronic design automation, p.566-572, June 1988
	J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976
	Chia-Jeng Tseng , Daniel P. Siewiorek, Facet: A procedure for the automated synthesis of digital systems, Proceedings of the 20th conference on Design automation, p.490-496, June 27-29, 1983, Miami Beach, Florida, United States
	P. W. Finn , L. E. Kavraki , J.-C. Latombe , R. Motwani , C. Shelton , S. Venkatasubramanian , A. Yao, RAPID: randomized pharmacophore identification for drug design, Proceedings of the thirteenth annual symposium on Computational geometry, p.324-333, June 04-06, 1997, Nice, France
	Behnak Yaltaghian , Mark Chignell, Re-ranking search results using network analysis a case study with google: a case study with Google, Proceedings of the 2002 conference of the Centre for Advanced Studies on Collaborative research, p.14, September 30-October 03, 2002, Toronto, Ontario, Canada
	Andreas Zeller, Isolating cause-effect chains from computer programs, ACM SIGSOFT Software Engineering Notes, v.27 n.6, November 2002
	Qinghua Zou , Wesley Chu , David Johnson , Henry Chiu, A pattern decomposition algorithm for data mining of frequent patterns, Knowledge and Information Systems, v.4 n.4, p.466-482, October 2002
	Jianliang Xu , Dik L. Lee , Bo Li, On bandwidth allocation for data dissemination in cellular mobile networks, Wireless Networks, v.9 n.2, p.103-116, March 2003
	Behnak Yaltaghian , Mark Chignell, Searching the hypermedia web: improved topic distillation through network analytic relevance ranking, The New Review of Hypermedia and Multimedia, v.8 n.1, p.171-197, January 2003
	Volker Stix, Finding All Maximal Cliques in Dynamic Graphs, Computational Optimization and Applications, v.27 n.2, p.173-186, February 2004
	Rajiv Ramaswami , Kumar N. Sivarajan, Routing and wavelength assignment in all-optical networks, IEEE/ACM Transactions on Networking (TON), v.3 n.5, p.489-500, Oct. 1995
	K. S. Ramanatha , N. N. Biswas, Design of Crosspoint-Irredundant PLAs Using Minimal Number of Control Inputs, IEEE Transactions on Computers, v.37 n.9, p.1130-1134, September 1988
	S.-Y. Kung , S.-N. Jean , C.-W. Chang, Fault-Tolerant Array Processors Using Single-Track Switches, IEEE Transactions on Computers, v.38 n.4, p.501-514, April 1989
	K. C. Dukka Bahadur , Tatsuya Akutsu , Etsuji Tomita , Tomokazu Seki, Protein side-chain packing problem: a maximum edge-weight clique algorithmic approach, Proceedings of the second conference on Asia-Pacific bioinformatics, p.191-200, January 01, 2004, Dunedin, New Zealand
	Behnak Yaltaghian , Mark H. Chignell, Effect of different network analysis strategies on search engine re-ranking, Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, p.308-317, October 04-07, 2004, Markham, Ontario, Canada
	R. Alvarez-Valdes , F. Parreño , J. M. Tamarit, A branch-and-cut algorithm for the pallet loading problem, Computers and Operations Research, v.32 n.11, p.3007-3029, November 2005
	Andreas Zeller, Isolating cause-effect chains from computer programs, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA
	Evgeny B. Krissinel , Kim Henrick, Common subgraph isomorphism detection by backtracking search, Software—Practice & Experience, v.34 n.6, p.591-607, May 2004
	Wei-Jen Li , Shlomo Hershkop , Salvatore J. Stolfo, Email archive analysis through graphical visualization, Proceedings of the 2004 ACM workshop on Visualization and data mining for computer security, October 29-29, 2004, Washington DC, USA
	Nuria Oliver , Greg Smith , Chintan Thakkar , Arun C. Surendran, SWISH: semantic analysis of window titles and switching history, Proceedings of the 11th international conference on Intelligent user interfaces, January 29-February 01, 2006, Sydney, Australia
	Mehmet Koyuturk , Ananth Grama , Naren Ramakrishnan, Compression, Clustering, and Pattern Discovery in Very High-Dimensional Discrete-Attribute Data Sets, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.447-461, April 2005
	Jinze Liu , Qi Zhang , Wei Wang , Leonard McMillan , Jan Prins, Clustering pair-wise dissimilarity data into partially ordered sets, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Roberto Santana, Estimation of Distribution Algorithms with Kikuchi Approximations, Evolutionary Computation, v.13 n.1, p.67-97, January 2005
	Zi Huang , Xiaofang Zhou , Dawei Song , Peter Bruza, Dimensionality reduction in patch-signature based protein structure matching, Proceedings of the 17th Australasian Database Conference, p.89-97, January 16-19, 2006, Hobart, Australia
	Saumitra M. Das , Dimitrios Koutsonikolas , Y. Charlie Hu, Practical service provisioning for wireless meshes, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York
	Himabindu Pucha , Y. Charlie Hu , Z. Morley Mao, On the impact of research network based testbeds on wide-area experiments, Proceedings of the 6th ACM SIGCOMM on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil
	M. A. Lozano , F. Escolano, Protein classification by matching and clustering surface graphs, Pattern Recognition, v.39 n.4, p.539-551, April, 2006
	Ryan McDonald , Fernando Pereira , Seth Kulick , Scott Winters , Yang Jin , Pete White, Simple algorithms for complex relation extraction with applications to biomedical IE, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.491-498, June 25-30, 2005, Ann Arbor, Michigan
	Etsuji Tomita , Akira Tanaka , Haruhisa Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, v.363 n.1, p.28-42, 25 October 2006
	Feng Gao , M. E. Woodward, A hybrid topological-stochastic partitioning method for scaling QoS routing algorithms, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.6, p.1705-1724, April, 2007
	Rajarshi Gupta , John Musacchio , Jean Walrand, Sufficient rate constraints for QoS flows in ad-hoc networks, Ad Hoc Networks, v.5 n.4, p.429-443, May, 2007
	Hongkun Zhao , Weiyi Meng , Clement Yu, Automatic extraction of dynamic record sections from search engine result pages, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Mehmet Koyutürk , Ananth Grama , Naren Ramakrishnan, Nonorthogonal decomposition of binary matrices for bounded-error data compression and analysis, ACM Transactions on Mathematical Software (TOMS), v.32 n.1, p.33-69, March 2006
	Salvatore J. Stolfo , Shlomo Hershkop , Chia-Wei Hu , Wei-Jen Li , Olivier Nimeskern , Ke Wang, Behavior-based modeling and its application to Email analysis, ACM Transactions on Internet Technology (TOIT), v.6 n.2, p.187-221, May 2006
	Daniel G. Brown , Ian M. Harrower, Integer Programming Approaches to Haplotype Inference by Pure Parsimony, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.3 n.2, p.141-154, April 2006
	Zhiping Zeng , Jianyong Wang , Lizhu Zhou , George Karypis, Out-of-core coherent closed quasi-clique mining from large dense graph databases, ACM Transactions on Database Systems (TODS), v.32 n.2, p.13-es, June 2007
	Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Detectives: detecting coalition hit inflation attacks in advertising networks streams, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Glaydston Mattos Ribeiro , Luiz Antonio Nogueira Lorena, Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem, Computers and Operations Research, v.34 n.9, p.2695-2708, September, 2007
	Yun Zhang , Faisal N. Abu-Khzam , Nicole E. Baldwin , Elissa J. Chesler , Michael A. Langston , Nagiza F. Samatova, Genome-Scale Computational Approaches to Memory-Intensive Applications in Systems Biology, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.12, November 12-18, 2005
	Nils Weskamp , Eyke Hullermeier , Daniel Kuhn , Gerhard Klebe, Multiple Graph Alignment for the Structural Analysis of Protein Active Sites, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.2, p.310-320, April 2007
	Christine Gaspin, RNA Secondary Structure Determination and Representation Based on Constraints Satisfaction, Constraints, v.6 n.2-3, p.201-221, June 2001
	F. Corno , P. Prinetto , M. Sonza Reorda, Using symbolic techniques to find the maximum clique in very large sparse graphs, Proceedings of the 1995 European conference on Design and Test, p.320, March 06-09, 1995
	Ryan Rowe , German Creamer , Shlomo Hershkop , Salvatore J Stolfo, Automated social hierarchy detection through email network analysis, Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis, p.109-117, August 12-12, 2007, San Jose, California
	Thomas Zimmermann , Nachiappan Nagappan, Predicting defects using network analysis on dependency graphs, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany
	Avaneendra Gupta , Siang-Chun The , John P. Hayes, XPRESS: A Cell Layout Generator with Integrated Transistor Folding, Proceedings of the 1996 European conference on Design and Test, p.393, March 11-14, 1996
	R. Su , W. M. Wonham, Supervisor Reduction for Discrete-Event Systems, Discrete Event Dynamic Systems, v.14 n.1, p.31-53, January 2004
	Immanuel M. Bomze, Evolution towards the Maximum Clique, Journal of Global Optimization, v.10 n.2, p.143-164, March 1997
	Peter Willett, From chemical documentation to chemoinformatics: 50 years of chemical information science, Journal of Information Science, v.34 n.4, p.477-499, August 2008
	S. Oliveira , S. -C. Seok, Multilevel approaches for large-scale proteomic networks, International Journal of Computer Mathematics, v.84 n.5, p.683-695, May 2007
	Frédéric Chazal , Leonidas J. Guibas , Steve Y. Oudot , Primoz Skraba, Analysis of scalar fields over point cloud data, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1021-1030, January 04-06, 2009, New York, New York
	Yida Wang , Ee-Peng Lim , San-Yih Hwang, Efficient algorithms for mining maximal valid groups, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.3, p.515-535, May 2008
	Tom Erik Julsrud , Per Morten Schiefloe, The development, distribution and maintenance of trust in distributed work groups: a social network approach, International Journal of Networking and Virtual Organisations, v.4 n.4, p.351-368, November 2007
	Tom Erik Julsrud, Flows, bridges and brokers: exploring the development of trust relations in a distributed work group, International Journal of Networking and Virtual Organisations, v.5 n.1, p.83-102, December 2008
	Joachim Dahl , Lieven Vandenberghe , Vwani Roychowdhury, Covariance selection for nonchordal graphs via chordal embedding, Optimization Methods & Software, v.23 n.4, p.501-520, August 2008
	Nan Du , Bai Wang , Bin Wu, Overlapping community structure detection in networks, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	M. A. Stefanone , G. Gay, Structural reproduction of social networks in computer-mediated communication forums, Behaviour & Information Technology, v.27 n.2, p.97-106, March 2008
	F. Cazals , C. Karande, Note: A note on the problem of reporting maximal cliques, Theoretical Computer Science, v.407 n.1-3, p.564-568, November, 2008
	Matthew C. Schmidt , Nagiza F. Samatova , Kevin Thomas , Byung-Hoon Park, A scalable, parallel algorithm for maximal clique enumeration, Journal of Parallel and Distributed Computing, v.69 n.4, p.417-428, April, 2009
	Samuel Rota Bulò , Andrea Torsello , Marcello Pelillo, A game-theoretic approach to partial clique enumeration, Image and Vision Computing, v.27 n.7, p.911-922, June, 2009
	Nan Du , Bai Wang , Bin Wu, Community detection in complex networks, Journal of Computer Science and Technology, v.23 n.4, p.672-683, July 2008
	Incheol Shin , Yilin Shen , Ying Xuan , My Tra Thai , Taieb Znati, Reactive jamming attacks in multi-radio wireless sensor networks: an efficient mitigating measure by identifying trigger nodes, Proceedings of the 2nd ACM international workshop on Foundations of wireless ad hoc and sensor networking and computing, May 18-18, 2009, New Orleans, Louisiana, USA
	Axel Kohnert , Sascha Kurz, Integral point sets over Znm, Discrete Applied Mathematics, v.157 n.9, p.2105-2117, May, 2009
	Nam H. Pham , Hoan Anh Nguyen , Tung Thanh Nguyen , Jafar M. Al-Kofahi , Tien N. Nguyen, Complete and accurate clone detection in graph-based models, Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, p.276-286, May 16-24, 2009
	Etsuji Tomita , Hiroaki Nakanishi, Polynomial-time solvability of the maximum clique problem, Proceedings of the 3rd international conference on European computing conference, p.203-208, June 26-28, 2009, Tbilisi, Georgia

INDEX TERMS

Keywords:
backtracking algorithm, branch and bound technique, cliques, clusters, maximal complete subgraphs, recursion

Collaborative Colleagues:

Coen Bron: colleagues

Joep Kerbosch: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player