Maximum weightk-independent set problem on permutation graphs
From MaRDI portal
Publication:4467342
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)
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
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A sequential algorithm for finding a maximum weightK-independent set on interval graphs
- An Optimal Algorithm for the Maximum Two-Chain Problem
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
- Faster algorithms for the shortest path problem
- Finding a maximum independent set in a permutation graph
- Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
- Solving the single step graph searching problem by solving the maximum two-independent set problem
- The NP-completeness column: an ongoing guide
- The maximum k-colorable subgraph problem for chordal graphs
- The weighted maximum independent set problem in permutation graphs
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Transitive Orientation of Graphs and Identification of Permutation Graphs
Cited in
(19)- An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
- “Rent-or-Buy” Scheduling and Cost Coloring Problems
- Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
- Finding cliques of maximum weight on a generalization of permutation graphs
- The exact weighted independent set problem in perfect graphs and related classes
- Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey
- Just-in-time scheduling with controllable processing times on parallel machines
- \(L(0,1)\)-labelling of permutation graphs
- An efficient PRAM algorithm for maximum-weight independent set on permutation graphs
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- MAXIMUM INDEPENDENT SET OF A PERMUTATION GRAPH IN K TRACKS
- Maximum \(k\)-covering of weighted transitive graphs with applications
- The just-in-time scheduling problem in a flow-shop scheduling system
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
- Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
- Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
- Graphs without large apples and the maximum weight independent set problem
- The weighted maximum independent set problem in 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)
