کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950738 1440715 2016 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The parameterised complexity of list problems on graphs of bounded treewidth
ترجمه فارسی عنوان
پیچیدگی پارامتریک از مشکلات لیست در نمودارهای عرض درختی محدود است
کلمات کلیدی
پیچیدگی پارامتریک، عرض درخت محدود. رنگ آمیزی نمودار، فهرست رنگ آمیزی، مسیر همیلتون،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,