کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10151238 | 685009 | 2018 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Meta-kernelization using well-structured modulators
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We develop a class of parameters which are based on a more general view on modulators: instead of size, the parameters employ a combination of rank-width and split decompositions to measure structure inside the modulator. This allows us to lift kernelization results from modulator-size to more general parameters, hence providing small kernels even in cases where previously developed approaches could not be applied. We show (i)Â how such large but well-structured modulators can be efficiently approximated, (ii)Â how they can be used to obtain polynomial kernels for graph problems expressible in Monadic Second Order logic, and (iii)Â how they support the extension of previous results in the area of structural meta-kernelization.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 248, 30 October 2018, Pages 153-167
Journal: Discrete Applied Mathematics - Volume 248, 30 October 2018, Pages 153-167
نویسندگان
Eduard Eiben, Robert Ganian, Stefan Szeider,