Multicoloring trees

Magnús M. Halldórsson; Guy Kortsarz; Andrzej Proskurowski; Ravit Salman; Hadas Shachnai; Jan Arne Telle

doi:10.1016/S0890-5401(02)00032-9

Multicoloring trees

Magnús M. Halldórsson, Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, Jan Arne Telle

Rutgers Camden, Computer Science

Research output: Contribution to journal › Article › peer-review

24 Scopus citations

Abstract

Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case.

Original language	English (US)
Pages (from-to)	113-129
Number of pages	17
Journal	Information and Computation
Volume	180
Issue number	2
DOIs	https://doi.org/10.1016/S0890-5401(02)00032-9
State	Published - Jan 29 2003

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Computer Science Applications
Computational Theory and Mathematics

Keywords

Approximation algorithms
Multicoloring
Resource allocation
Scheduling

Access to Document

10.1016/S0890-5401(02)00032-9

Cite this

@article{9316ba59b56e425790ec8d0cc22c8596,

title = "Multicoloring trees",

abstract = "Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case.",

keywords = "Approximation algorithms, Multicoloring, Resource allocation, Scheduling",

author = "Halld{\'o}rsson, {Magn{\'u}s M.} and Guy Kortsarz and Andrzej Proskurowski and Ravit Salman and Hadas Shachnai and Telle, {Jan Arne}",

year = "2003",

month = jan,

day = "29",

doi = "10.1016/S0890-5401(02)00032-9",

language = "English (US)",

volume = "180",

pages = "113--129",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "2",

}

TY - JOUR

T1 - Multicoloring trees

AU - Halldórsson, Magnús M.

AU - Kortsarz, Guy

AU - Proskurowski, Andrzej

AU - Salman, Ravit

AU - Shachnai, Hadas

AU - Telle, Jan Arne

PY - 2003/1/29

Y1 - 2003/1/29

N2 - Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case.

AB - Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case.

KW - Approximation algorithms

KW - Multicoloring

KW - Resource allocation

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=0037471702&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037471702&partnerID=8YFLogxK

U2 - 10.1016/S0890-5401(02)00032-9

DO - 10.1016/S0890-5401(02)00032-9

M3 - Article

AN - SCOPUS:0037471702

SN - 0890-5401

VL - 180

SP - 113

EP - 129

JO - Information and Computation

JF - Information and Computation

IS - 2

ER -

Multicoloring trees

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this