On generating all maximal independent sets. (English) Zbl 0654.68086

We present an algorithm that generates all maximal independent sets of a graph in lexicographic order, with only polynomial delay between the output of two successive independent sets. We also show that there is no polynomial-delay algorithm for generating all maximal independent sets in reverse lexicographic order, unless \(P=NP\).


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Aho, A. V.; Szymanski, T.; Yannakakis, M., Sorting the Cartesian product, (Proc. Conf. on Information Sciences and Systems (1980), Princeton University: Princeton University Princeton, NJ), 557-558
[3] Garcia-Molina, H.; Barbara, D., How to assign votes in a distributed system, J. ACM, 32, 841-860 (1985) · Zbl 0633.68109
[4] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Generating all maximal independent sets: NP-hardness and polynomial-time algorithms, SIAM J. Comput., 9, 558-565 (1980) · Zbl 0445.68054
[5] Paull, M. C.; Unger, S. H., Minimizing the number of states in incompletely specified sequential switching functions, IRE Trans. Electr. Comput., EC-8, 356-367 (1959)
[6] Read, R. C., Every one a winner, or how to avoid isomorphism when cataloguing combinatorial configurations, Ann. Discrete Math., 2, 107-120 (1978) · Zbl 0392.05001
[7] Read, R. C.; Tarjan, R. E., Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks, 5, 237-252 (1975) · Zbl 0316.05125
[8] Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all maximal independent sets, SIAM J. Comput., 6, 505-517 (1977) · Zbl 0364.05027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.