Multi-coloring trees

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

doi:10.1007/3-540-48686-0_27

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)	https://doi.org/10.1007/3-540-48686-0_27
סטטוס פרסום	פורסם - 1999
אירוע	5th Annual International Conference on Computing and Combinatorics, COCOON 1999 - Tokyo, יפן משך הזמן: 26 יולי 1999 → 28 יולי 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/99 → 28/07/99

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

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.

גישה למסמך

10.1007/3-540-48686-0_27

קבצים וקישורים אחרים

Link to publication in Scopus

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

Halldórsson, M. M., Kortsarz, G., Proskurowski, A., Salman, R., Shachnai, H., & Telle, J. A. (1999). Multi-coloring trees. ב- S. Nakano, H. Imai, D. T. Lee, T. Tokuyama, & T. Asano (עורכים), Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings (עמודים 271-280). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); כרך 1627). Springer Verlag. https://doi.org/10.1007/3-540-48686-0_27

Halldórsson, Magnús M. ; Kortsarz, Guy ; Proskurowski, Andrzej et al. / Multi-coloring trees. Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings. עורך / Shin-ichi Nakano ; Hideki Imai ; D.T. Lee ; Takeshi Tokuyama ; Takao Asano. Springer Verlag, 1999. עמודים 271-280 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{841e7c17e0e74daaaac46a0a914a037f,

title = "Multi-coloring trees",

abstract = "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.",

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

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 5th Annual International Conference on Computing and Combinatorics, COCOON 1999 ; Conference date: 26-07-1999 Through 28-07-1999",

year = "1999",

doi = "10.1007/3-540-48686-0\_27",

language = "אנגלית",

isbn = "3540662006",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "271--280",

editor = "Shin-ichi Nakano and Hideki Imai and D.T. Lee and Takeshi Tokuyama and Takao Asano",

booktitle = "Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings",

address = "גרמניה",

}

Halldórsson, MM, Kortsarz, G, Proskurowski, A, Salman, R, Shachnai, H & Telle, JA 1999, Multi-coloring trees. ב- S Nakano, H Imai, DT Lee, T Tokuyama & T Asano (עורכים), Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), כרך 1627, Springer Verlag, עמודים 271-280, 5th Annual International Conference on Computing and Combinatorics, COCOON 1999, Tokyo, יפן, 26/07/99. https://doi.org/10.1007/3-540-48686-0_27

Multi-coloring trees. / Halldórsson, Magnús M.; Kortsarz, Guy; Proskurowski, Andrzej et al.
Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings. עורך / Shin-ichi Nakano; Hideki Imai; D.T. Lee; Takeshi Tokuyama; Takao Asano. Springer Verlag, 1999. עמוד 271-280 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); כרך 1627).

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

TY - GEN

T1 - Multi-coloring trees

AU - Halldórsson, Magnús M.

AU - Kortsarz, Guy

AU - Proskurowski, Andrzej

AU - Salman, Ravit

AU - Shachnai, Hadas

AU - Telle, Jan Arne

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/22644449071

U2 - 10.1007/3-540-48686-0_27

DO - 10.1007/3-540-48686-0_27

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:22644449071

SN - 3540662006

SN - 9783540662006

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 271

EP - 280

BT - Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings

A2 - Nakano, Shin-ichi

A2 - Imai, Hideki

A2 - Lee, D.T.

A2 - Tokuyama, Takeshi

A2 - Asano, Takao

PB - Springer Verlag

T2 - 5th Annual International Conference on Computing and Combinatorics, COCOON 1999

Y2 - 26 July 1999 through 28 July 1999

ER -

Halldórsson MM, Kortsarz G, Proskurowski A, Salman R, Shachnai H, Telle JA. Multi-coloring trees. ב- Nakano S, Imai H, Lee DT, Tokuyama T, Asano T, עורכים, Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings. Springer Verlag. 1999. עמוד 271-280. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-48686-0_27

Multi-coloring trees

תקציר

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

כנס

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

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

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