Bron–Kerbosch algorithm
In computer science, the Bron–Kerbosch algorithm is an enumeration algorithm for finding all maximal cliques in an undirected graph. That is, it lists all subsets of vertices with the two properties that each pair of vertices in one of the listed subsets is connected by an edge, and no listed subset can have any additional vertices added to it while preserving its complete connectivity. The Bron–Kerbosch algorithm was designed by Dutch scientists Coenraad Bron and , who published its description in 1973.
- Comment
- enIn computer science, the Bron–Kerbosch algorithm is an enumeration algorithm for finding all maximal cliques in an undirected graph. That is, it lists all subsets of vertices with the two properties that each pair of vertices in one of the listed subsets is connected by an edge, and no listed subset can have any additional vertices added to it while preserving its complete connectivity. The Bron–Kerbosch algorithm was designed by Dutch scientists Coenraad Bron and , who published its description in 1973.
- Depiction
- Has abstract
- enIn computer science, the Bron–Kerbosch algorithm is an enumeration algorithm for finding all maximal cliques in an undirected graph. That is, it lists all subsets of vertices with the two properties that each pair of vertices in one of the listed subsets is connected by an edge, and no listed subset can have any additional vertices added to it while preserving its complete connectivity. The Bron–Kerbosch algorithm was designed by Dutch scientists Coenraad Bron and , who published its description in 1973. Although other algorithms for solving the clique problem have running times that are, in theory, better on inputs that have few maximal independent sets, the Bron–Kerbosch algorithm and subsequent improvements to it are frequently reported as being more efficient in practice than the alternatives. It is well-known and widely used in application areas of graph algorithms such as computational chemistry. A contemporaneous algorithm of , although presented in different terms, can be viewed as being the same as the Bron–Kerbosch algorithm, as it generates the same search tree.
- Hypernym
- Algorithm
- Is primary topic of
- Bron–Kerbosch algorithm
- Label
- enBron–Kerbosch algorithm
- Link from a Wikipage to an external page
- gist.github.com/abhin4v/8304062
- gitlab.com/Gluttton/BronKerbosch
- www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf
- github.com/atulsingh7890/Graph/blob/master/Graph.cpp
- web.archive.org/web/20131029201831/http:/www.kuchaev.com/files/graph.py
- davidpynes.github.io/Tutorials/Graphs/Graph_03/
- github.com/skilla/maximal-cliques
- github.com/darrenstrash/quick-cliques
- www.dcs.gla.ac.uk/~pat/jchoco/clique/enumeration/report.pdf
- Link from a Wikipage to another Wikipage
- Backtracking
- Category:Articles with example pseudocode
- Category:Graph algorithms
- Clique (graph theory)
- Clique problem
- Coenraad Bron
- Complete graph
- Computational chemistry
- Computer science
- Degeneracy (graph theory)
- Degree (graph theory)
- Empty set
- Enumeration algorithm
- File:6n-graf.svg
- Glossary of graph theory
- Graph (discrete mathematics)
- Graph algorithm
- Israel Journal of Mathematics
- Joep Kerbosch
- Linear time
- Neighborhood (graph theory)
- Netherlands
- Output-sensitive algorithm
- Polynomial time
- Power of three
- Recursion
- Social network
- Sparse graph
- Subset
- SameAs
- Algorithme de Bron-Kerbosch
- Bron–Kerboš algoritam
- m.05h4g5w
- Q2031707
- wSbA
- Алгоритм Брона — Кербоша
- Алгоритм Брона — Кербоша
- ขั้นตอนวิธีโบรน-เคอร์โบสท์
- Subject
- Category:Articles with example pseudocode
- Category:Graph algorithms
- Thumbnail
- WasDerivedFrom
- Bron–Kerbosch algorithm?oldid=1110744344&ns=0
- WikiPageLength
- 16104
- Wikipage page ID
- 21480757
- Wikipage revision ID
- 1110744344
- WikiPageUsesTemplate
- Template:Citation
- Template:Harvtxt
- Template:Math
- Template:Refbegin
- Template:Refend
- Template:Reflist
