Bron-Kerbosch maximal independent set and maximal clique algorithms

Lists all the maximal independent sets and the maximal cliques of an undirected graph

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