Maximum weightk-independent set problem on permutation graphs

DOI10.1080/00207160310001614972zbMath1100.68597MaRDI QIDQ4467342

Madhumangal Pal, Anita Saha

Publication date: 9 June 2004

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

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

zbMATH Keywords

design of algorithms; network flow problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

90B35: Deterministic scheduling theory in operations research

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

“Rent-or-Buy” Scheduling and Cost Coloring Problems, Fixed interval scheduling: models, applications, computational complexity and algorithms, Selection of programme slots of television channels for giving advertisement: a graph theoretic approach, Just-in-time scheduling with controllable processing times on parallel machines, An efficient PRAM algorithm for maximum-weight independent set on permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding a maximum independent set in a permutation graph
• The maximum k-colorable subgraph problem for chordal graphs
• Solving the single step graph searching problem by solving the maximum two-independent set problem
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• The weighted maximum independent set problem in permutation graphs
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• Faster algorithms for the shortest path problem
• The NP-completeness column: an ongoing guide
• An Optimal Algorithm for the Maximum Two-Chain Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Transitive Orientation of Graphs and Identification of Permutation Graphs