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
المعرِّفات الرقمية للأشياء	https://doi.org/10.1007/3-540-48686-0_27
حالة النشر	نُشِر - 1999
الحدث	5th Annual International Conference on Computing and Combinatorics, COCOON 1999 - Tokyo, اليابان المدة: ٢٦ يوليو ١٩٩٩ → ٢٨ يوليو ١٩٩٩

سلسلة المنشورات

الاسم	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت	1627
رقم المعيار الدولي للدوريات (المطبوع)	0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)	1611-3349

!!Conference

!!Conference	5th Annual International Conference on Computing and Combinatorics, COCOON 1999
الدولة/الإقليم	اليابان
المدينة	Tokyo
المدة	٢٦/٠٧/٩٩ → ٢٨/٠٧/٩٩

ملاحظة ببليوغرافية

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 وآخرون. / 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, اليابان, ٢٦/٠٧/٩٩. https://doi.org/10.1007/3-540-48686-0_27

Multi-coloring trees. / Halldórsson, Magnús M.; Kortsarz, Guy; Proskurowski, Andrzej وآخرون.
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 - http://www.scopus.com/inward/record.url?scp=22644449071&partnerID=8YFLogxK

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

ملخص

سلسلة المنشورات

!!Conference

ملاحظة ببليوغرافية

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا