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 graph, respectively.
The input to the functions is the adjacency matrix of the desired 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 |
