# MPI-I-2003-1-015

## Sum-Multicoloring on paths

### Kovács, Annamaria

**MPI-I-2003-1-015**. July** **2003, 20 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 302 KBytes; 298 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-015

**BibTeX**
`@TECHREPORT{``Kovács2003``,`

` 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},`

`}`