An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
From MaRDI portal
Publication:1199945
Recommendations
- A faster algorithm for maximum independent set on interval filament graphs
- Algorithms and Computation
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
- Maximum weightk-independent set problem on permutation graphs
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3706451 (Why is no real title available?)
- A new polynomial-time algorithm for linear programming
- An Optimal Algorithm for the Maximum Two-Chain Problem
- 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
- `` Strong NP-Completeness Results
Cited in
(35)- Layered graphs: applications and algorithms
- A faster algorithm for maximum independent set on interval filament graphs
- An optimal time algorithm for finding a maximum weight independent set in a tree
- The just-in-time scheduling problem in a flow-shop scheduling system
- A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
- A sequential algorithm for finding a maximum weightK-independent set on interval graphs
- Maximum weightk-independent set problem on permutation graphs
- Packing boundary-anchored rectangles and squares
- An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
- Powers of geometric intersection graphs and dispersion algorithms
- Faster algorithms for some optimization problems on collinear points
- A unified model and algorithms for temporal map labeling
- Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- The stable set problem and the thinness of a graph
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- A parllel algorithm for finding a maximum weight clique of an interval graph
- Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
- Robust maximum weighted independent-set problems on interval graphs
- Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
- An algorithm for finding a maximum weighted independent set in an arbitrary graph
- Maximum independent set for intervals by divide and conquer with pruning
- Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
- Complexity results on restricted instances of a paint shop problem for words
- An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- A polynomial algorithm for the k-cluster problem on the interval graphs
- Heuristics for the connected assignment problem in arrays
- Just-in-time scheduling with controllable processing times on parallel machines
- Managing platelet supply through improved routing of blood collection vehicles
- Maximum weight independent set of circular-arc graph and its application
- Efficient computation of tolerances in the weighted independent set problem for some classes of graphs
- New results on induced matchings
- A matrix characterization of interval and proper interval graphs
- An algorithm for the maximum weight independent set problem on outerstring graphs
This page was built for publication: An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199945)
