A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically

In this paper we present a depth first search algorithm to generate the family of maximal independent sets of an undirected graph lexicographically. Extensive computational experience on more than 1000 randomly generated graphs ranging from 20 to 220 vertices and from 20% to 90% density has shown that the proposed algorithm is (a) two to fifteen times faster than the Bron and Kerbosch algorithm and (b) at least three times faster than the algorithm of Tsukiyamaet al. and becomes increasingly more efficient as both the density and size of the graph increase. A further characteristic of the proposed algorithm is that it employs four one-dimensional arrays of working computer memory only, each of which has length equal to the number of vertices of the graph.