The weighted maximum independent set problem in permutation graphs

DOI10.1007/BF01994845zbMath0757.68065OpenAlexW2000281299MaRDI QIDQ1195927

Gen-Huey Chen, Chang Wu Yu

Publication date: 26 January 1993

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01994845

zbMATH Keywords

maximum independent setCREW PRAMpermutation graphCRCW PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Distributed algorithms (68W15)

Related Items

Solving the anti-covering location problem using Lagrangian relaxation, A parallel algorithm to generate all maximal independent sets on permutation graphs, Facets for node packing, Maximum weightk-independent set problem on permutation graphs, An efficient PRAM algorithm for maximum-weight independent set on permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Scanline algorithms on a grid
• Finding a minimum independent dominating set in a permutation graph
• On Comparability and Permutation Graphs
• Domination in permutation graphs
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• Transitive Orientation of Graphs and Identification of Permutation Graphs