The weighted maximum independent set problem in permutation graphs
From MaRDI portal
Publication:1195927
DOI10.1007/BF01994845zbMath0757.68065OpenAlexW2000281299MaRDI QIDQ1195927
Publication date: 26 January 1993
Published in: BIT (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01994845
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