MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


Sum-Multicoloring on paths

Kovács, Annamaria

July 2003, 20 pages.

Status: available - back from printing

The question, whether the preemptive Sum Multicoloring (pSMC) problem is hard on paths was raised by Halldorsson et al. ["Multi-coloring trees", Information and Computation, 180(2):113-129,2002]. The pSMC problem is a scheduling problem where the pairwise conflicting jobs are represented by a conflict graph, and the time lengths of jobs by integer weights on the nodes. The goal is to schedule the jobs so that the sum of their finishing times is minimized. In the paper we give an O(n^3p) time algorithm for the pSMC problem on paths, where n is the number of nodes and p is the largest time length. The result easily carries over to cycles.

  • Attachement: (302 KBytes); MPI-I-2003-1-015.pdf (298 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Kov{\'a}cs, Annamaria},
  TITLE = {Sum-Multicoloring on paths},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2003-1-015},
  MONTH = {July},
  YEAR = {2003},
  ISSN = {0946-011X},