کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951265 | 1441199 | 2017 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Kernelization using structural parameters on sparse graph classes
ترجمه فارسی عنوان
کرنل کردن با استفاده از پارامترهای ساختاری بر روی کلاسهای گراف درشت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی پارامتریک، کرنل کردن، هیچ جایی نمودار نیست شاخص عددی محدود درختکاری
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove that graph problems with finite integer index have linear kernels on graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For nowhere dense graph classes, our result yields almost-linear kernels. We also argue that such a linear kernelization result with a weaker parameter would fail to include some of the problems covered by our framework. We only require the problems to have FII on graphs of constant treedepth. This allows to prove linear kernels also for problems such as Longest-Path/Cycle, Exact-s,t-Path, Treewidth, and Pathwidth, which do not have FII on general graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 84, March 2017, Pages 219-242
Journal: Journal of Computer and System Sciences - Volume 84, March 2017, Pages 219-242
نویسندگان
Jakub Gajarský, Petr HlinÄný, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar,