Maximum weightk-independent set problem on permutation graphs
DOI10.1080/00207160310001614972zbMATH Open1100.68597OpenAlexW2127101641MaRDI QIDQ4467342FDOQ4467342
Authors: 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
Recommendations
- Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- The weighted maximum independent set problem in permutation graphs
- scientific article; zbMATH DE number 3943870
- An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Finding a maximum independent set in a permutation graph
- The maximum k-colorable subgraph problem for chordal graphs
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- Faster algorithms for the shortest path problem
- Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
- A sequential algorithm for finding a maximum weightK-independent set on interval graphs
- The NP-completeness column: an ongoing guide
- The weighted maximum independent set problem in permutation graphs
- Solving the single step graph searching problem by solving the maximum two-independent set problem
- An Optimal Algorithm for the Maximum Two-Chain Problem
- Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
Cited In (19)
- The just-in-time scheduling problem in a flow-shop scheduling system
- “Rent-or-Buy” Scheduling and Cost Coloring Problems
- The weighted maximum independent set problem in permutation graphs
- Graphs without large apples and the maximum weight independent set problem
- An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
- Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey
- MAXIMUM INDEPENDENT SET OF A PERMUTATION GRAPH IN K TRACKS
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- Maximum \(k\)-covering of weighted transitive graphs with applications
- Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
- \(L(0,1)\)-labelling of permutation graphs
- Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
- The exact weighted independent set problem in perfect graphs and related classes
- Just-in-time scheduling with controllable processing times on parallel machines
- Finding cliques of maximum weight on a generalization of permutation graphs
- An efficient PRAM algorithm for maximum-weight independent set on permutation graphs
- Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
This page was built for publication: Maximum weightk-independent set problem on permutation graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4467342)
