کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952321 1364440 2017 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
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
نویسندگان
, , , ,