Generating all maximal independent sets on trees in lexicographic order

DOI10.1016/0020-0255(94)90013-2MaRDI QIDQ1328528zbMATH OpenOpenAlexFDO

Authors V. Pereyra

Publication date 14 September 1995

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0255(94)90013-2

zbMATH Keywords

lexicographic ordermaximal independent setsNP- completepolynomial time delay

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Generate all maximal independent sets in permutation graphs
• A parallel algorithm to generate all maximal independent sets on permutation graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• The Number of Maximal Independent Sets in a Tree

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithm 457: finding all cliques of an undirected graph
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3446921 (Why is no real title available?)
• Independent domination in chordal graphs
• On generating all maximal independent sets

Cited in

(1)

• On generating all maximal independent sets

Describes a project that uses

Uses Software

• Algorithm 457

This page was built for publication: Generating all maximal independent sets on trees in lexicographic order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1328528)