A New Algorithm for Generating All the Maximal Independent Sets

The problem of generating all the maximal independent sets (or maximal cliques) of a given graph is fundamental in graph theory and is also one of the most important in terms of the application of graph theory. In this paper, we present a new efficient algorithm for generating all the maximal independent sets, for which processing time and memory space are bounded by O(nmμ) and $O(n+m)$, respectively, where n, m, and μ are the numbers of vertices, edges, and maximal independent sets of a graph.