Bron-Kerbosch maximal independent set and maximal clique algorithms
Maximal Independent Sets and Maximal Cliques are useful in many applications. The naive way of listing them can be very computationally intensive. This package contains two functions, BK_MaxIS and BK_MaxClique, that use the Bron-Kerbosch algorithm to list all the maximal independent sets and maximal cliques of a given undirected graph, respectively.
The input to the functions is the adjacency matrix of the desired undirected graph (http://mathworld.wolfram.com/AdjacencyMatrix.html).
The return value is a 0-1 matrix, where each column corresponds to a maximal matching, and each row to a vertex. The size of the matrix is thus m*n, where m is the number of vertices in the graph, and n is the number of maximal independent sets. A value of 1 in position (i,j) indicates that vertex i is active in the maximal independent set (or clique) indexed by column j.
Examples:
To find the maximal independent sets of a 3-path:
>> A = [0 1 0;1 0 1;0 1 0]
>> BK_MaxIS(A)
ans =
1 0
0 1
1 0
To find the maximal cliques of a 4-cycle C_4:
>> A = [0 1 0 1;1 0 1 0;0 1 0 1;1 0 1 0];
>> BK_MaxClique(A)
ans =
1 1 0 0
1 0 1 0
0 0 1 1
0 1 0 1
引用格式
Berk Birand (2024). Bron-Kerbosch maximal independent set and maximal clique algorithms (https://www.mathworks.com/matlabcentral/fileexchange/24591-bron-kerbosch-maximal-independent-set-and-maximal-clique-algorithms), MATLAB Central File Exchange. 检索来源 .
MATLAB 版本兼容性
平台兼容性
Windows macOS Linux类别
标签
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!BKmaximal/
版本 | 已发布 | 发行说明 | |
---|---|---|---|
1.5.0.0 | Updated description to specify this is for undirected graphs |
||
1.4.0.0 | Fixed a small bug for obtaining the neighbors of a node. Also added the maximal clique function that uses the complement of a graph. |
||
1.3.0.0 | Fixed the duplicates in the file. |
||
1.2.0.0 | Removed the dependency on Matgraph. Only the adjacency matrix of the graph is now needed to compute the independent sets. |
||
1.0.0.0 |