Bron-Kerbosch maximal clique finding algorithm

Implementation of the Bron-Kerbosch algorithm to find all maximal cliques of an undirected graph.

Description

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

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Maximal Cliques, Bron-Kerbosch maximal independent set and maximal clique algorithms, Maximal Independent Sets using JGraphT

• MATLAB release: MATLAB 7.12 (2011a)

[Akli Benali]

 

[Akli Benali]

Very nice work. The function is very fast, efficient and accurate. When compared with the one posted by Ahmad, it is about 1000 times faster.

[Edmund Brekke]

 

[Habib]

Very nice work. How can one modify the code in order to limit the number of maximal cliques found so far. That is, one may need only a subset of maximal cliques and only the number of them is important but not specified ones.