Bron-Kerbosch maximal clique finding algorithm

Version 1.2.0.0 (2,68 ko) par Jeffrey Wildman
Implementation of the Bron-Kerbosch algorithm to find all maximal cliques of an undirected graph.
4.9
(8)
3,1K téléchargements
Mise à jour 27 oct. 2011

Afficher la licence

[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.

Citation pour cette source

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. Récupéré le .

Compatibilité avec les versions de MATLAB
Créé avec R2011a
Compatible avec toutes les versions
Plateformes compatibles
Windows macOS Linux
Catégories
En savoir plus sur Undirected Graphs dans Help Center et MATLAB Answers

Community Treasure Hunt

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

Start Hunting!

Version Publié le Notes de version
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