An efficient algorithm for finding a maximum weight 2-independent set on interval graphs

DOI10.1016/0020-0190(92)90216-IzbMath0764.68073MaRDI QIDQ1199945

Chuan Yi Tang, Ruay-Shiung Chang, Ju-Yuan Hsiao

Publication date: 17 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

algorithm; maximum weight \(k\)-independent set problem; interval graph; maximum weight independent set problem; maximum weight 2-independent set problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

68R10: Graph theory (including graph drawing) in computer science

Related Items

Maximum weightk-independent set problem on permutation graphs, An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs, Fixed interval scheduling: models, applications, computational complexity and algorithms, Just-in-time scheduling with controllable processing times on parallel machines, Powers of geometric intersection graphs and dispersion algorithms, New results on induced matchings, A matrix characterization of interval and proper interval graphs, Complexity results on restricted instances of a paint shop problem for words, The stable set problem and the thinness of a graph, A sequential algorithm for finding a maximum weightK-independent set on interval graphs, 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