کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950738 | 1440715 | 2016 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The parameterised complexity of list problems on graphs of bounded treewidth
ترجمه فارسی عنوان
پیچیدگی پارامتریک از مشکلات لیست در نمودارهای عرض درختی محدود است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی پارامتریک، عرض درخت محدود. رنگ آمیزی نمودار، فهرست رنگ آمیزی، مسیر همیلتون،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the parameterised complexity of several list problems on graphs, with parameter treewidth or pathwidth. In particular, we show that List Edge Chromatic Number and List Total Chromatic Number are fixed parameter tractable, parameterised by treewidth, whereas List Hamilton Path is W[1]-hard, even parameterised by pathwidth. These results resolve two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen (2011).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 251, December 2016, Pages 91-103
Journal: Information and Computation - Volume 251, December 2016, Pages 91-103
نویسندگان
Kitty Meeks, Alexander Scott,