Multi-coloring trees

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

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

Scheduling jobs with pairwise conflicts is modeled by the graph multi-coloring problem. It occurs in two versions: preemptive and non-preemptive. We study these problems 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.

שפה מקוריתאנגלית
כותר פרסום המארחComputing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings
עורכיםShin-ichi Nakano, Hideki Imai, D.T. Lee, Takeshi Tokuyama, Takao Asano
מוציא לאורSpringer Verlag
עמודים271-280
מספר עמודים10
מסת"ב (מודפס)3540662006, 9783540662006
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1999
אירוע5th Annual International Conference on Computing and Combinatorics, COCOON 1999 - Tokyo, יפן
משך הזמן: 26 יולי 199928 יולי 1999

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך1627
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס5th Annual International Conference on Computing and Combinatorics, COCOON 1999
מדינה/אזוריפן
עירTokyo
תקופה26/07/9928/07/99

הערה ביבליוגרפית

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Multi-coloring trees'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי