On generating all maximal independent sets (Q1108809): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(3 intermediate revisions by 3 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0020-0190(88)90065-8 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2007940874 / rank
 
Normal rank
Property / Wikidata QID
 
Property / Wikidata QID: Q56210424 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4773298 / rank
 
Normal rank
Property / cites work
 
Property / cites work: How to assign votes in a distributed system / rank
 
Normal rank
Property / cites work
 
Property / cites work: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: A New Algorithm for Generating All the Maximal Independent Sets / rank
 
Normal rank

Latest revision as of 17:59, 18 June 2024

scientific article
Language Label Description Also known as
English
On generating all maximal independent sets
scientific article

    Statements

    On generating all maximal independent sets (English)
    0 references
    0 references
    0 references
    1988
    0 references
    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\).
    0 references
    enumeration
    0 references
    NP-complete
    0 references
    independent sets
    0 references
    lexicographic order
    0 references

    Identifiers