Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Polynomial Time Preemptive Sum-Multicoloring on Paths
verfasst von : Annamária Kovács
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The
preemptive Sum-Multicoloring (pSMC)
problem is a scheduling problem where pairwise conflicting jobs are represented by a conflict graph. The time demands of jobs are given by integer weights on the nodes. The goal is to schedule the jobs in such a way that the
sum
of their finish times is minimized. We give an
${\mathcal O}(n \cdot {\rm min}(n,{\rm log}\ p))$
time algorithm for pSMC on paths and cycles, where
n
is the number of nodes and
p
is the largest time demand. This is the first polynomial algorithm for this problem. It answers the question raised in [8] about the hardness of this problem. In this respect our result identifies a gap between binary-tree conflict graphs – where the question is NP-hard – and paths. Furthermore, our time bound gets very close to that of
${\mathcal O}(n\cdot {\rm log} \ p/{\rm log log} \ p)$
for the
non-preemptive
SMC on paths [8] . A detailed version of this paper is available at [3].