Improved kernel results for some FPT problems based on simple observations Academic Article

abstract

• 2016 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 G7Graphs 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.

authors

• Chen, Jianer

published proceedings

• THEORETICAL COMPUTER SCIENCE

author list (cited authors)

• Li, W., Feng, Q., Chen, J., & Hu, S.

citation count

• 13

complete list of authors

• Li, Wenjun||Feng, Qilong||Chen, Jianer||Hu, Shuai

publication date

• January 2017

publisher

• Elsevier  Publisher

published in

• Theoretical Computer Science  Journal

keywords

• Fixed-parameter Tractability
• Kernelization
• Np-hard

Digital Object Identifier (DOI)

• 10.1016/j.tcs.2016.06.012

start page

• 20

end page

• 27

volume

• 657

URL

• http://dx.doi.org/10.1016/j.tcs.2016.06.012