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
מזהי עצם דיגיטלי (DOIs)	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, ארצות הברית משך הזמן: 8 אוג׳ 1999 → 11 אוג׳ 1999

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

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

כנס

כנס	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
תקופה	8/08/99 → 11/08/99

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

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{2cc17fe108c3463ab63636085217cd9e,

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, ארצות הברית, 8/08/99. 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 - https://www.scopus.com/pages/publications/0013291627

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

תקציר

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

כנס

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

גישה למסמך

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

טביעת אצבע

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