کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435665 689924 2015 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
ترجمه فارسی عنوان
الگوریتم تقریبی کارآمد برای رنگ آمیزی چند رنگی پراکندگی گراف
کلمات کلیدی
رنگ آمیزی نمودار، پهنای باند چند رنگی متوالی، الگوریتم تقریبی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let G be a graph in which each vertex v   has a positive integer weight b(v)b(v) and each edge (v,w)(v,w) has a nonnegative integer weight b(v,w)b(v,w). A bandwidth consecutive multicoloring, simply called a b-coloring of G, assigns each vertex v   a specified number b(v)b(v) of consecutive positive integers as colors of v   so that, for each edge (v,w)(v,w), all integers assigned to vertex v differ from all integers assigned to vertex w   by more than b(v,w)b(v,w). The maximum integer assigned to vertices is called the span of the coloring. The b-coloring problem asks to find a b-coloring of a given graph G with the minimum span. In the paper, we present four efficient approximation algorithms for the problem, which have theoretical performance guarantees for the computation time, the span of a found b-coloring and the approximation ratio. We also obtain several upper bounds on the minimum span, expressed in terms of the maximum b-degrees, one of which is an extension of Brooks' theorem on an ordinary coloring.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 607, Part 2, 23 November 2015, Pages 208–220
نویسندگان
, ,