کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431300 688499 2014 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bounded max-colorings of graphs
ترجمه فارسی عنوان
حداکثر رنگ آمیزی گراف ها محدود شده است
کلمات کلیدی
حداکثر رنگ آمیزی رنگ آمیزی محدود پیچیدگی، الگوریتم تقریبی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In a bounded max-coloring of a vertex/edge weighted graph, each color class is of cardinality at most b and of weight equal to the weight of the heaviest vertex/edge in this class. The bounded max-vertex/edge-coloring problems ask for such a coloring minimizing the sum of all color classes' weights. These problems generalize the well known max-coloring problems by taking into account the number of available resources (i.e., the cardinality of color classes) in practical applications. In this paper we present complexity results and approximation algorithms for the bounded max-coloring problems on general graphs, bipartite graphs and trees.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 26, May 2014, Pages 56–68
نویسندگان
, , , ,