Bron-Kerbosch maximal independent set algorithm (Scripts) Publisher's description
from Berk Birand
Maximal independent sets come in handy for certain applications
Maximal independent sets come in handy for certain applications. The Bron-Kerbosch algorithm is a well-known algorithm for listing all the maximal independent sets (originally for finding maximal cliques, which is the same as finding the maximal independent sets in the complement). This file is an implementation of this algorithm. The only argument is the adjacency matrix of the desired graph.
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 number j.
System Requirements:MATLAB 7.7 (R2008b)
Program Release Status: Major Update
Program Install Support: Install and Uninstall