Maximum weightk-independent set problem on permutation graphs

DOI10.1080/00207160310001614972zbMath1100.68597OpenAlexW2127101641MaRDI QIDQ4467342

Anita Saha, Madhumangal Pal

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 algorithmsnetwork flow problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (10)

Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ \(L(0,1)\)-labelling of permutation graphs ⋮ Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey ⋮ The just-in-time scheduling problem in a flow-shop scheduling system ⋮ Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems ⋮ Just-in-time scheduling with controllable processing times on parallel machines ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ “Rent-or-Buy” Scheduling and Cost Coloring Problems ⋮ 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

This page was built for publication: Maximum weightk-independent set problem on permutation graphs