Generating all maximal independent sets on trees in lexicographic order

DOI10.1016/0020-0255(94)90013-2zbMath0820.90112OpenAlexW2154008162MaRDI QIDQ1328528

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)

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• On generating all maximal independent sets
• Independent domination in chordal graphs
• 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
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• A New Algorithm for Generating All the Maximal Independent Sets
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
• Algorithm 457: finding all cliques of an undirected graph

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