Generate all maximal independent sets in permutation graphs

DOI10.1080/00207169308804157zbMath0824.68091OpenAlexW2068025855WikidataQ59409907 ScholiaQ59409907MaRDI QIDQ4323409

Chang Wu Yu, Gen-Huey Chen

Publication date: 16 February 1995

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207169308804157

zbMATH Keywords

permutation graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (6)

Coloring permutation graphs in parallel ⋮ Maximal independent sets in grid graphs ⋮ Listing Maximal Independent Sets with Minimal Space and Bounded Delay ⋮ A parallel algorithm to generate all maximal independent sets on permutation graphs ⋮ Maximal independent sets in caterpillar graphs ⋮ An efficient algorithm to generate all maximal independent sets on trapezoid graphs

Cites Work

• Decomposing a set of points into chains, with applications to permutation and circle graphs
• Bipartite permutation graphs
• On domination problems for permutation and other graphs
• Finding a minimum independent dominating set in a permutation graph
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• On Comparability and Permutation Graphs
• Domination in permutation graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Generate all maximal independent sets in permutation graphs