Svoboda | Graniru | BBC Russia | Golosameriki | Facebook
skip to main content
Advanced Search

Algorithm 457: finding all cliques of an undirected graph

Authors: Coen Bron, Joep KerboschAuthors Info & Claims
Communications of the ACM, Volume 16, Issue 9
Pages 575 - 577
https://doi.org/10.1145/362342.362367
Published: 01 September 1973 Publication History
Metrics
Total Citations1,791
Total Downloads13,347
Last 12 Months1,033
Last 6 weeks119
PDFeReader
First page of PDF

References

[1]
Augustson, J.G., and Minker, J. An analysis of some graph theoretical cluster techniques, J. ACM 17 (1970), 571-588.
Digital Library
Google Scholar
[2]
Bierstone, E. Unpublished report. U of Toronto.
Google Scholar
[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.
Google Scholar
[4]
Little, John D.C., et al. An algorithm for the traveling salesman problem. Oper. Res. 11 (1963), 972-989.
Digital Library
Google Scholar
[5]
Moon, J.W., and Moser, L. On cliques in graphs. Israel J. Math. 3 (1965), 23-28.
Crossref
Google Scholar
[6]
Mulligan, G.D., and Corneil, D.G. Corrections to Bierstone's algorithm for generating cliques. J. ACM 19 (Apr. 1972), 244-247.
Digital Library
Google Scholar

Cited By

View all
  • Choi IKim W(2024)Enhancing Exchange-Traded Fund Price Predictions: Insights from Information-Theoretic Networks and Node EmbeddingsEntropy10.3390/e2601007026:1(70)Online publication date: 12-Jan-2024
    https://doi.org/10.3390/e26010070
  • Mahmoud RCasadebaig PHilgert NGaudio N(2024)A workflow for processing global datasets: application to intercroppingPeer Community Journal10.24072/pcjournal.3894Online publication date: 29-Feb-2024
    https://doi.org/10.24072/pcjournal.389
  • Chang LGamage RYu J(2024)Efficient k-Clique Count Estimation with Accuracy GuaranteeProceedings of the VLDB Endowment10.14778/3681954.368203217:11(3707-3719)Online publication date: 1-Jul-2024
    https://dl.acm.org/doi/10.14778/3681954.3682032
  • Show More Cited By

Recommendations

  • Cliques in the union of graphs

    Let B and R be two simple graphs with vertex set V, and let G ( B , R ) be the simple graph with vertex set V, in which two vertices are adjacent if they are adjacent in at least one of B and R. For X V , we denote by B | X the subgraph of B induced by ...

  • Extremal graphs for intersecting cliques

    For any two positive integers n r 1, the well-known Turán Theorem states that there exists a least positive integer ex(n,Kr) such that every graph with n vertices and ex(n,Kr)+1 edges contains a subgraph isomorphic to Kr. We determine the minimum number ...

  • On the Maximum Number of Cliques in a Graph

    A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-...

Comments

Information & Contributors

Information

Published In

Communications of the ACM  Volume 16, Issue 9
Sept. 1973
105 pages
ISSN:0001-0782
EISSN:1557-7317
DOI:10.1145/362342
Issue’s Table of Contents
Copyright © 1973 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1973
Published in CACM Volume 16, Issue 9

Permissions

Request permissions for this article.
Request Permissions

Check for updates

Author Tags

  1. backtracking algorithm
  2. branch and bound technique
  3. cliques
  4. clusters
  5. maximal complete subgraphs
  6. recursion

Qualifiers

  • Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1,033
  • Downloads (Last 6 weeks)119
Reflects downloads up to 25 Aug 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all
  • Choi IKim W(2024)Enhancing Exchange-Traded Fund Price Predictions: Insights from Information-Theoretic Networks and Node EmbeddingsEntropy10.3390/e2601007026:1(70)Online publication date: 12-Jan-2024
    https://doi.org/10.3390/e26010070
  • Mahmoud RCasadebaig PHilgert NGaudio N(2024)A workflow for processing global datasets: application to intercroppingPeer Community Journal10.24072/pcjournal.3894Online publication date: 29-Feb-2024
    https://doi.org/10.24072/pcjournal.389
  • Chang LGamage RYu J(2024)Efficient k-Clique Count Estimation with Accuracy GuaranteeProceedings of the VLDB Endowment10.14778/3681954.368203217:11(3707-3719)Online publication date: 1-Jul-2024
    https://dl.acm.org/doi/10.14778/3681954.3682032
  • Zhou YFang YMa CHou THuang X(2024)Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information NetworksProceedings of the VLDB Endowment10.14778/3681954.368197517:11(2946-2959)Online publication date: 1-Jul-2024
    https://dl.acm.org/doi/10.14778/3681954.3681975
  • Liu CPeng ZZheng WZou L(2024)FSM: A Fine-Grained Splitting and Merging Framework for Dual-Balanced Graph PartitionProceedings of the VLDB Endowment10.14778/3665844.366586417:9(2378-2391)Online publication date: 1-May-2024
    https://dl.acm.org/doi/10.14778/3665844.3665864
  • Carchiolo VGrassia MMalgeri MMangioni G(2024)Geometric Deep Learning sub-network extraction for Maximum Clique EnumerationPLOS ONE10.1371/journal.pone.029618519:1(e0296185)Online publication date: 16-Jan-2024
    https://doi.org/10.1371/journal.pone.0296185
  • 陈 书(2024)Fuzzy Instance Space Co-Location Pattern Mining Algorithm Based on Voronoi Graph and Distance Attenuation EffectHans Journal of Data Mining10.12677/hjdm.2024.14200614:02(65-80)Online publication date: 2024
    https://doi.org/10.12677/hjdm.2024.142006
  • Weekx STal GVanhaverbeke L(2024)How Many More Public Charging Stations Do We Need? A Data-Driven Approach Considering Charging Station Overflow DynamicsTransportation Research Record: Journal of the Transportation Research Board10.1177/03611981241242081Online publication date: 25-Apr-2024
    https://doi.org/10.1177/03611981241242081
  • Vandierendonck H(2024)Differentiating Set Intersections in Maximal Clique Enumeration by Function and Subproblem SizeProceedings of the 38th ACM International Conference on Supercomputing10.1145/3650200.3656607(150-163)Online publication date: 30-May-2024
    https://dl.acm.org/doi/10.1145/3650200.3656607
  • Marchetti KSevaljevic ADiviney AEardley CPhillips RKhadka RIgbokwe DBodily PMonga MLonati VBarendsen ESheard JPaterson J(2024)Redux: An Interactive, Dynamic Knowledge Base for Teaching NP-completenessProceedings of the 2024 on Innovation and Technology in Computer Science Education V. 110.1145/3649217.3653544(255-261)Online publication date: 3-Jul-2024
    https://dl.acm.org/doi/10.1145/3649217.3653544
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Full Access

Get this Article

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media

Download PDF
View Issue’s Table of Contents