Multicoloring trees

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

Research output: Contribution to journalArticlepeer-review

23 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 languageEnglish (US)
Pages (from-to)113-129
Number of pages17
JournalInformation and Computation
Volume180
Issue number2
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Multicoloring trees'. Together they form a unique fingerprint.

Cite this