Bron-Kerbosch maximal clique finding algorithm

バージョン 1.2.0.0 (2.68 KB) 作成者: Jeffrey Wildman
Implementation of the Bron-Kerbosch algorithm to find all maximal cliques of an undirected graph.
4.9
(8)
ダウンロード: 3.1K
更新 2011/10/27

ライセンスの表示

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

引用

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. 取得済み .

MATLAB リリースの互換性
作成: R2011a
すべてのリリースと互換性あり
プラットフォームの互換性
Windows macOS Linux
カテゴリ
Help Center および MATLAB Answers で Undirected Graphs についてさらに検索

Community Treasure Hunt

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

Start Hunting!

バージョン 公開済み リリース ノート
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