Multicoloring planar graphs and partial k-trees

Magnús M. Halldórsson; Guy Kortsarz

doi:10.1007/978-3-540-48413-4_8

Multicoloring planar graphs and partial k-trees

Magnús M. Halldórsson, Guy Kortsarz

מדעי המחשב

نتاج البحث: فصل من :كتاب / تقرير / مؤتمر › منشور من مؤتمر › مراجعة النظراء

ملخص

We study the multicoloring problem with two objective functions: minimizing the makespan and minimizing the multisum. We focus on partial k-trees and planar graphs. In particular, we give polynomial time approximation schemes (PTAS) for both classes, for both preemptive and non-preemptive multisum colorings.

اللغة الأصلية	الإنجليزيّة
عنوان منشور المضيف	Randomization, Approximation, and Combinatorial Optimization
العنوان الفرعي لمنشور المضيف	Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings
المحررون	Jose D. P. Rolim, Alistair Sinclair, Dorit Hochbaum, Klaus Jansen
ناشر	Springer Verlag
الصفحات	73-84
عدد الصفحات	12
رقم المعيار الدولي للكتب (المطبوع)	3540663290, 9783540663294
المعرِّفات الرقمية للأشياء	https://doi.org/10.1007/978-3-540-48413-4_8
حالة النشر	نُشِر - 1999
الحدث	3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999 - Berkeley, الولايات المتّحدة المدة: ٨ أغسطس ١٩٩٩ → ١١ أغسطس ١٩٩٩

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

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

!!Conference

!!Conference	3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999
الدولة/الإقليم	الولايات المتّحدة
المدينة	Berkeley
المدة	٨/٠٨/٩٩ → ١١/٠٨/٩٩

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

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.

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

10.1007/978-3-540-48413-4_8

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

Link to publication in Scopus

قم بذكر هذا

Halldórsson, M. M., & Kortsarz, G. (1999). Multicoloring planar graphs and partial k-trees. في J. D. P. Rolim, A. Sinclair, D. Hochbaum, & K. Jansen (المحررون), Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings (الصفحات 73-84). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); المجلد 1671). Springer Verlag. https://doi.org/10.1007/978-3-540-48413-4_8

Halldórsson, Magnús M. ; Kortsarz, Guy. / Multicoloring planar graphs and partial k-trees. Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. محرر / Jose D. P. Rolim ; Alistair Sinclair ; Dorit Hochbaum ; Klaus Jansen. Springer Verlag, 1999. الصفحات 73-84 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a67c6ba1ac8c454495cbfbc072a8962a,

title = "Multicoloring planar graphs and partial k-trees",

abstract = "We study the multicoloring problem with two objective functions: minimizing the makespan and minimizing the multisum. We focus on partial k-trees and planar graphs. In particular, we give polynomial time approximation schemes (PTAS) for both classes, for both preemptive and non-preemptive multisum colorings.",

author = "Halld{\'o}rsson, {Magn{\'u}s M.} and Guy Kortsarz",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999 ; Conference date: 08-08-1999 Through 11-08-1999",

year = "1999",

doi = "10.1007/978-3-540-48413-4_8",

language = "אנגלית",

isbn = "3540663290",

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

publisher = "Springer Verlag",

pages = "73--84",

editor = "Rolim, {Jose D. P.} and Alistair Sinclair and Dorit Hochbaum and Klaus Jansen",

booktitle = "Randomization, Approximation, and Combinatorial Optimization",

address = "גרמניה",

}

Halldórsson, MM & Kortsarz, G 1999, Multicoloring planar graphs and partial k-trees. في JDP Rolim, A Sinclair, D Hochbaum & K Jansen (المحررون), Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), المجلد 1671, Springer Verlag, الصفحات 73-84, 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Berkeley, الولايات المتّحدة, ٨/٠٨/٩٩. https://doi.org/10.1007/978-3-540-48413-4_8

Multicoloring planar graphs and partial k-trees. / Halldórsson, Magnús M.; Kortsarz, Guy.
Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. محرر / Jose D. P. Rolim; Alistair Sinclair; Dorit Hochbaum; Klaus Jansen. Springer Verlag, 1999. صفحة 73-84 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); المجلد 1671).

نتاج البحث: فصل من :كتاب / تقرير / مؤتمر › منشور من مؤتمر › مراجعة النظراء

TY - GEN

T1 - Multicoloring planar graphs and partial k-trees

AU - Halldórsson, Magnús M.

AU - Kortsarz, Guy

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

PY - 1999

Y1 - 1999

N2 - We study the multicoloring problem with two objective functions: minimizing the makespan and minimizing the multisum. We focus on partial k-trees and planar graphs. In particular, we give polynomial time approximation schemes (PTAS) for both classes, for both preemptive and non-preemptive multisum colorings.

AB - We study the multicoloring problem with two objective functions: minimizing the makespan and minimizing the multisum. We focus on partial k-trees and planar graphs. In particular, we give polynomial time approximation schemes (PTAS) for both classes, for both preemptive and non-preemptive multisum colorings.

UR - http://www.scopus.com/inward/record.url?scp=0013291627&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-48413-4_8

DO - 10.1007/978-3-540-48413-4_8

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

AN - SCOPUS:0013291627

SN - 3540663290

SN - 9783540663294

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

SP - 73

EP - 84

BT - Randomization, Approximation, and Combinatorial Optimization

A2 - Rolim, Jose D. P.

A2 - Sinclair, Alistair

A2 - Hochbaum, Dorit

A2 - Jansen, Klaus

PB - Springer Verlag

T2 - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999

Y2 - 8 August 1999 through 11 August 1999

ER -

Halldórsson MM, Kortsarz G. Multicoloring planar graphs and partial k-trees. في Rolim JDP, Sinclair A, Hochbaum D, Jansen K, المحررون, Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. Springer Verlag. 1999. صفحة 73-84. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-48413-4_8

Multicoloring planar graphs and partial k-trees

ملخص

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

!!Conference

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

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

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

بصمة

قم بذكر هذا