Maximum weightk-independent set problem on permutation graphs
From MaRDI portal
Publication:4467342
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35)
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
- A sequential algorithm for finding a maximum weightK-independent set on interval graphs
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- An Optimal Algorithm for the Maximum Two-Chain Problem
- 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
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 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 maximum k-colorable subgraph problem for chordal graphs
- The NP-completeness column: an ongoing guide
- 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
(20)- The weighted maximum independent set problem in permutation graphs
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- Maximum \(k\)-covering of weighted transitive graphs with applications
- Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
- Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
- Finding cliques of maximum weight on a generalization of permutation graphs
- Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
- An efficient PRAM algorithm for maximum-weight independent set on 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
- The just-in-time scheduling problem in a flow-shop scheduling system
- MAXIMUM INDEPENDENT SET OF A PERMUTATION GRAPH IN K TRACKS
- “Rent-or-Buy” Scheduling and Cost Coloring Problems
- An efficient algorithm for finding a maximum weight k-independent set of trapezoid graphs
- The parallel stack loading problem: polynomial solvability in the unlimited-capacity case and exact approaches for the finite-capacity case
- Graphs without large apples and the maximum weight independent set problem
- 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
- Just-in-time scheduling with controllable processing times on parallel machines
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)
