Generate all maximal independent sets in permutation graphs

DOI10.1080/00207169308804157MaRDI QIDQ4323409zbMATH OpenOpenAlexWikidataFDO

Authors C. W. 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)

Recommendations

• A parallel algorithm to generate all maximal independent sets on permutation graphs
• On generating all maximal independent sets
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• scientific article; zbMATH DE number 434864
• An efficient PRAM algorithm for maximum-weight independent set on permutation graphs

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• Bipartite permutation graphs
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• Domination in permutation graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Finding a minimum independent dominating set in a permutation graph
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3299758 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• On Comparability and Permutation Graphs
• On domination problems for permutation and other graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(11)

• Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
• Generating all maximal independent sets on trees in lexicographic order
• Coloring permutation graphs in parallel
• Maximal independent sets in grid graphs
• scientific article; zbMATH DE number 434864 (Why is no real title available?)
• A general method for generating all maximal independent sets of a graph
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• MAXIMUM INDEPENDENT SET OF A PERMUTATION GRAPH IN K TRACKS
• A parallel algorithm to generate all maximal independent sets on permutation graphs
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Maximal independent sets in caterpillar graphs

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

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