On generating all maximal independent sets
type: Item
instance of: scholarly article
title: On generating all maximal independent sets
zbMATH Open document ID: 0654.68086
DOI: 10.1016/0020-0190(88)90065-8
author: D. S. Johnson
author: Mihalis Yannakakis
author: Christos Papadimitriou
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4068316
zbMATH Keywords: enumeration
zbMATH Keywords: NP-complete
zbMATH Keywords: independent sets
zbMATH Keywords: lexicographic order
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90065-8
OpenAlex ID: W2007940874
Wikidata QID: Q56210424
cites work: Q4773298
cites work: How to assign votes in a distributed system
cites work: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
cites work: Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
cites work: Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
cites work: A New Algorithm for Generating All the Maximal Independent Sets
Recommended article: A generalization of maximal independent sets
Recommended article: On the maximum number of maximum independent sets
Recommended article: Q3641025
Recommended article: Q4304413
Recommended article: Generating all maximal independent sets on trees in lexicographic order
Recommended article: Maximizing the Number of Independent Sets of a Fixed Size
Recommended article: Q4486258
Recommended article: Critical and maximum independent sets revisited
Recommended article: Maximum independent sets near the upper bound
Recommended article: Q4864968
description: scientific article; zbMATH DE number 4068316