کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874207 | 1441029 | 2018 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Path multicoloring in spider graphs with even color multiplicity
ترجمه فارسی عنوان
مسیر رنگ آمیزی در گراف های عنکبوتی با رنگ چندگانه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
چند رنگ رنگ مسیر، نمودار عنکبوتی الگوریتم ها،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We give an exact polynomial-time algorithm for the problem of coloring a collection of paths defined on a spider graph using a minimum number of colors (Min-PMC), while respecting a given even maximum admissible color multiplicity on each edge. This complements a previous result on the complexity of Min-PMC in spider graphs, where it was shown that, for every odd k, the problem is NP-hard in spiders with admissible color multiplicity k on each edge. We also obtain an exact polynomial-time algorithm for maximizing the number of colored paths with a given number of colors (Max-PMC) in spider graphs with even admissible color multiplicity on each edge.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 133, May 2018, Pages 1-4
Journal: Information Processing Letters - Volume 133, May 2018, Pages 1-4
نویسندگان
Evangelos Bampas, Christina Karousatou, Aris Pagourtzis, Katerina Potika,