کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949886 | 1364262 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Treewidth and Pathwidth parameterized by the vertex cover number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
After the number of vertices, Vertex Cover Number is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover Number. Here we consider the treewidth and pathwidth problems parameterized by k, the size of a minimum vertex cover of the input graph. We show that the pathwidth and treewidth can be computed in Oâ(3k) time. This complements recent polynomial kernel results for treewidth and pathwidth parameterized by the Vertex Cover Number.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 114-129
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 114-129
نویسندگان
Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, Yngve Villanger,