Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs

DOI10.1016/0020-0190(93)90188-FzbMath0768.68191MaRDI QIDQ1210310

Ming-Shing Yu, Shoe-Jane Chang, Lin Yu Tseng

Publication date: 23 May 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

sequential algorithmparallel algorithmpermutation graphmaximum-weight independent set problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Finding a Maximum Clique in a Grounded 1-Bend String Graph ⋮ A parallel algorithm to generate all maximal independent sets on permutation graphs ⋮ Maximum weightk-independent set problem on permutation graphs ⋮ Constrained tree inclusion ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs ⋮ The maximum clique problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding a maximum independent set in a permutation graph
• Preserving order in a forest in less than logarithmic time and linear space
• On Comparability and Permutation Graphs
• Design and implementation of an efficient priority queue
• Transitive Orientation of Graphs and Identification of Permutation Graphs

This page was built for publication: Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs