کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
439347 | 690530 | 2006 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimum sum multicoloring on the edges of trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The edge multicoloring problem is that given a graph G and integer demands x(e) for every edge e, assign a set of x(e) colors to edge e, such that adjacent edges have disjoint sets of colors. In the minimum sum edge multicoloring problem the finish time of an edge is defined to be the highest color assigned to it. The goal is to minimize the sum of the finish times. The main result of the paper is a polynomial-time approximation scheme for minimum sum multicoloring the edges of trees. We also show that the problem is strongly NP-hard for trees, even if every demand is at most 2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 361, Issues 2–3, 1 September 2006, Pages 133-149
Journal: Theoretical Computer Science - Volume 361, Issues 2–3, 1 September 2006, Pages 133-149