An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
From MaRDI portal
Publication:1199945
DOI10.1016/0020-0190(92)90216-IzbMath0764.68073MaRDI QIDQ1199945
Chuan Yi Tang, Ju-Yuan Hsiao, Ruay-Shiung Chang
Publication date: 17 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
algorithmmaximum weight \(k\)-independent set probleminterval graphmaximum weight independent set problemmaximum weight 2-independent set problem
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
A linear-time algorithm for the weighted feedback vertex problem on interval graphs, The stable set problem and the thinness of a graph, Managing platelet supply through improved routing of blood collection vehicles, Fixed interval scheduling: models, applications, computational complexity and algorithms, Heuristics for the connected assignment problem in arrays, Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey, An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs, 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, Powers of geometric intersection graphs and dispersion algorithms, A sequential algorithm for finding a maximum weightK-independent set on interval graphs, New results on induced matchings, A matrix characterization of interval and proper interval graphs, A unified model and algorithms for temporal map labeling, Just-in-time scheduling with controllable processing times on parallel machines, Complexity results on restricted instances of a paint shop problem for words, Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs, Layered graphs: applications and algorithms, Unnamed Item, Packing boundary-anchored rectangles and squares, Maximum weightk-independent set problem on permutation graphs, Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity, A polynomial algorithm for the k-cluster problem on the interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- A new polynomial-time algorithm for linear programming
- The maximum k-colorable subgraph problem for chordal graphs
- Solving the single step graph searching problem by solving the maximum two-independent set problem
- The NP-completeness column: an ongoing guide
- An Optimal Algorithm for the Maximum Two-Chain Problem
- `` Strong NP-Completeness Results
