Bron-Kerbosch maximal clique finding algorithm

Versione 1.2.0.0 (2,68 KB) da Jeffrey Wildman
Implementation of the Bron-Kerbosch algorithm to find all maximal cliques of an undirected graph.
4.9
(8)
3,1K download
Aggiornato 27 ott 2011

Visualizza la licenza

[MC] = MAXIMALCLIQUES(A,V_STR) Given a graph's boolean adjacency matrix, A, find all maximal cliques on A using the Bron-Kerbosch algorithm in a recursive manner.

V_STR is an optional input string with the version of the Bron-Kerbosch algorithm to be used (either 'v1' or 'v2'). Version 2 is faster (and default), and version 1 is included for posterity.

The output matrix MC contains the maximal cliques in its columns.

Note: This function can be used to compute the maximal independent sets of a graph A by providing the complement of A as the input graph.

Note: This function can be used to compute the maximal matchings of a graph A by providing the complement of the line graph of A as the input graph.

Ref: Bron, Coen and Kerbosch, Joep, "Algorithm 457: finding all cliques of an undirected graph", Communications of the ACM, vol. 16, no. 9, pp: 575–577, September 1973.

Ref: Cazals, F. and Karande, C., "A note on the problem of reporting maximal cliques", Theoretical Computer Science (Elsevier), vol. 407, no. 1-3, pp: 564-568, November 2008.

Cita come

Jeffrey Wildman (2024). Bron-Kerbosch maximal clique finding algorithm (https://www.mathworks.com/matlabcentral/fileexchange/30413-bron-kerbosch-maximal-clique-finding-algorithm), MATLAB Central File Exchange. Recuperato .

Compatibilità della release di MATLAB
Creato con R2011a
Compatibile con qualsiasi release
Compatibilità della piattaforma
Windows macOS Linux
Categorie
Scopri di più su Undirected Graphs in Help Center e MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Versione Pubblicato Note della release
1.2.0.0

Updated: 10/27/2011 - updated documentation & removal of ~ punctuation to ignore function output arguments for better compatibility with older MATLAB versions prior to 2009b (Thanks to Akli Benali).
1.0.0.0