On generating all maximal independent sets

https://doi.org/10.1016/0020-0190(88)90065-8Get rights and content

Abstract

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.

References (8)

There are more references available in the full text version of this article.

Cited by (686)

  • Shortest distances as enumeration problem

    2024, Discrete Applied Mathematics
View all citing articles on Scopus
View full text