A New Algorithm for Generating All the Maximal Independent Sets
Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, Isao Shirakawa · SIAM Journal on Computing · 1977
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\mu)$ and $O(n+m)$, respectively, where n, m, and $\mu$ are the numbers of vertices, edges, and maximal independent sets of a graph.