کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874207 1441029 2018 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Path multicoloring in spider graphs with even color multiplicity
ترجمه فارسی عنوان
مسیر رنگ آمیزی در گراف های عنکبوتی با رنگ چندگانه
کلمات کلیدی
چند رنگ رنگ مسیر، نمودار عنکبوتی الگوریتم ها،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , ,