کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331893 | 686963 | 2015 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
ترجمه فارسی عنوان
پیچیدگی محاسباتی مشکل رنگ آمیزی ستون فقرات برای نمودارهای محدود با ستون فقرات متصل شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودارهای درجه محدود، شماره کروماتیک ستون فقرات، الگوریتم های گراف،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a graph G, a spanning subgraph H of G and an integer λâ¥2, a λ-backbone coloring of G with backbone H is a proper vertex coloring of G using colors 1,2,â¦, in which the color difference between vertices adjacent in H is greater than or equal to λ. The backbone coloring problem is that of finding such a coloring whose maximum color does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree graphs with connected backbones and we give a complete computational complexity classification of this problem. We present a polynomial algorithm for optimal backbone coloring for subcubic graphs with arbitrary backbones. We also prove that the backbone coloring problem for graphs with arbitrary backbones and with fixed maximum degree (at least 4) is NP-complete. Furthermore, we show that for the special case of graphs with fixed maximum degree at least 5 and λâ¥4 the problem remains NP-complete even for spanning tree backbones.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 232-236
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 232-236
نویسندگان
Robert Janczewski, Krzysztof Turowski,