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\mu)$ and $O(n+m)$, respectively, where n, m, and $\mu$ are the numbers of vertices, edges, and maximal independent sets of a graph.