A sequential algorithm for finding a maximum weightK-independent set on interval graphs

DOI10.1080/00207169608804486zbMath1001.68512OpenAlexW2111523610MaRDI QIDQ2710758

G. P. Bhattacharjee, Madhumangal Pal

Publication date: 19 December 2002

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207169608804486

zbMATH Keywords

combinatorial problemsanalysis of algorithmsdesign of algorithmsindependent setnetwork flow probleminterval graph

Mathematics Subject Classification ID

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

Related Items (16)

A linear time algorithm to compute square of interval graphs and their colouring ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Maximum weight independent set of circular-arc graph and its application ⋮ The off-line group seat reservation problem ⋮ Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey ⋮ 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 ⋮ Robust maximum weighted independent-set problems on interval graphs ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ \(L(2,1)\)-labeling of interval graphs ⋮ Just-in-time scheduling with controllable processing times on parallel machines ⋮ Complexity of the robust weighted independent set problems on interval graphs ⋮ Fast algorithms for identifying maximal common connected sets of interval graphs ⋮ Maximum weightk-independent set problem on permutation graphs ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs ⋮ An efficient algorithm to generate all maximal independent sets on trapezoid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The maximum k-colorable subgraph problem for chordal graphs
• Solving the single step graph searching problem by solving the maximum two-independent set problem
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Faster algorithms for the shortest path problem
• The NP-completeness column: an ongoing guide
• An Optimal Algorithm for the Maximum Two-Chain Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: A sequential algorithm for finding a maximum weightK-independent set on interval graphs