کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949508 | 1440192 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A tight lower bound for Vertex Planarization on graphs of bounded treewidth
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
One of the core technical contributions of the work of Jansen, Lokshtanov, and Saurabh is an algorithm that solves a weighted variant of Vertex Planarization in time 2O(wlogw)â
n on graphs of treewidth w. In this short note we prove that the running time of this routine is tight under the Exponential Time Hypothesis, even in unweighted graphs and when parameterizing by treedepth. Consequently, it is unlikely that a potential single-exponential algorithm for Vertex Planarization parameterized by the solution size can be obtained by merely improving upon the aforementioned bounded treewidth subroutine.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 231, 20 November 2017, Pages 211-216
Journal: Discrete Applied Mathematics - Volume 231, 20 November 2017, Pages 211-216
نویسندگان
Marcin Pilipczuk,