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

DOI10.1016/0020-0190(92)90216-IzbMATH Open0764.68073MaRDI QIDQ1199945FDOQ1199945

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

Publication date: 17 January 1993

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

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

A new polynomial-time algorithm for linear programming
Title not available (Why is that?)
The maximum k-colorable subgraph problem for chordal graphs
`` Strong NP-Completeness Results
Title not available (Why is that?)
The NP-completeness column: an ongoing guide
Solving the single step graph searching problem by solving the maximum two-independent set problem
An Optimal Algorithm for the Maximum Two-Chain Problem

Cited In (35)

A faster algorithm for maximum independent set on interval filament graphs
Layered graphs: applications and algorithms
An optimal time algorithm for finding a maximum weight independent set in a tree
Maximum weightk-independent set problem on permutation graphs
A sequential algorithm for finding a maximum weightK-independent set on interval graphs
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
Packing boundary-anchored rectangles and squares
An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
Faster algorithms for some optimization problems on collinear points
Powers of geometric intersection graphs and dispersion algorithms
A unified model and algorithms for temporal map labeling
Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey
The stable set problem and the thinness of a graph
Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
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
Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
Robust maximum weighted independent-set problems on 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
Managing platelet supply through improved routing of blood collection vehicles
Just-in-time scheduling with controllable processing times on parallel machines
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)