On generating all maximal independent sets
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\).
scientific article; zbMATH DE number 4068316
scientific article