کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4952321 1364440 2017 8 صفحه PDF ندارد دانلود کنید
عنوان انگلیسی مقاله
Improved kernel results for some FPT problems based on simple observations☆
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Improved kernel results for some FPT problems based on simple observations☆
چکیده انگلیسی

In this paper, we study the kernelization algorithms for several parameterized problems, including Parameterized Co-Path Set problem, Parameterized Path-Contractibility problem and Parameterized Connected Dominating Set on G7 Graphs problem. Based on simple observations, we give simple kernelization algorithms with kernel sizes 4k, 3k+4, and O(k2), respectively, which improves the previous best results 6k, 5k+3, and O(k3), respectively.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 657, Part A, 2 January 2017, Pages 20-27
نویسندگان
, , , ,