Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
From MaRDI portal
Publication:1879365
DOI10.1007/s00453-003-1031-8zbMath1069.68531OpenAlexW2012711355MaRDI QIDQ1879365
Guy Kortsarz, Magnús M. Halldórsson, Hadas Shachnai
Publication date: 22 September 2004
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-003-1031-8
Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)
Related Items (23)
On the performance guarantee of first fit for sum coloring ⋮ An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths ⋮ Vertex disjoint copies of \(K_{1 , 4}\) in claw-free graphs ⋮ The \(p\)-Maxian problem on interval graphs ⋮ Chromatic Edge Strength of Some Multigraphs ⋮ Min Sum Edge Coloring in Multigraphs Via Configuration LP ⋮ Minimum sum set coloring of trees and line graphs of trees ⋮ Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs ⋮ Improved bounds for randomized preemptive online matching ⋮ Backup 2-center on interval graphs ⋮ A branch-and-price algorithm for the minimum sum coloring problem ⋮ Minimum sum edge colorings of multicycles ⋮ Minimum sum multicoloring on the edges of trees ⋮ “Rent-or-Buy” Scheduling and Cost Coloring Problems ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms ⋮ On the minimum sum coloring of \(P_4\)-sparse graphs ⋮ Combinatorial algorithms for data migration to minimize average completion time ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Complexity results for minimum sum edge coloring ⋮ On sum coloring and sum multi-coloring for restricted families of graphs ⋮ Weighted sum coloring in batch scheduling of conflicting jobs ⋮ Minimum Sum Coloring of P4-sparse graphs ⋮ A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs
This page was built for publication: Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
