# Item

ITEM ACTIONSEXPORT

Released

Report

#### Sum-Multicoloring on paths

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

2003-1-015

(Any fulltext), 10KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Kovács, A.(2003). *Sum-Multicoloring on paths* (MPI-I-2003-1-015).
Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-6B18-C

##### Abstract

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.