Improved kernel results for some FPT problems based on simple observations

详细信息    查看全文

• 作者：Wenjun Li^a ; ^b ; Qilong Feng^a ; ^{csufeng@mail.csu.edu.cn} ; Jianer Chen^a ; ^c ; Shuai Hu^a
• 关键词：Fixed-parameter tractability ; NP-hard ; Kernelization
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：2 January 2017
• 年：2017
• 卷：657
• 期：part_PA
• 页码：20-27
• 全文大小：357 K
• 卷排序：657

文摘

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 G7G7 Graphs problem. Based on simple observations, we give simple kernelization algorithms with kernel sizes 4k  , 3k+43k+4, and O(k2)O(k2), respectively, which improves the previous best results 6k  , 5k+35k+3, and O(k3)O(k3), respectively.