Sum multi-coloring of graphs

Amotz Bar-Noy, Magnús M. Halldórsson, Guy Kortsarz, Ravit Salman, Hadas Shachnai

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


Scheduling dependent jobs on multiple machines is modeled by the graph multi-coloring problem. In this paper we consider the problem of minimizing the average completion time of all jobs. This is formalized as the sum multi-coloring (SMC) problem: Given a graph and the number of colors required by each vertex, find a multi-coloring which minimizes the sum of the largest colors assigned to the vertices. It reduces to the known sum coloring (SC) problem in the special case of unit execution times. This paper reports a comprehensive study of the SMC problem, treating three models: with and without preemption allowed, as well as co-scheduling where tasks cannot start while others are running. We establish a linear relation between the approximability of the maximum independent set (IS) and SMC in all three models, via a link to the SC problem. Thus, for classes of graphs where IS is p-approximable, we obtain O (p) -approximations for preemptive and co-scheduling SMC, and O(p • log n) for non-preemptive SMC. In addition, we give constant-approximation algorithms for SMC under different models, on a number of fundamental classes of graphs, including bipartite, line, bounded degree, and planar graphs.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAlgorithms - ESA 1999 - 7th Annual European Symposium, Proceedings
المحررونJaroslav Nešetřil
ناشرSpringer Verlag
عدد الصفحات12
رقم المعيار الدولي للكتب (المطبوع)3540662510, 9783540662518
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1999
الحدث7th Annual European Symposium on Algorithms, ESA 1999 - Prague, التشيك
المدة: ١٦ يوليو ١٩٩٩١٨ يوليو ١٩٩٩

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

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


!!Conference7th Annual European Symposium on Algorithms, ESA 1999

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

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.


أدرس بدقة موضوعات البحث “Sum multi-coloring of graphs'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا