Improved kernel results for some FPT problems based on simple observations
Improved kernel results for some FPT problems based on simple observations
复制标题
基于简单观察改进了一些 FPT 问题的核结果
DOI：
10.1016/j.tcs.2016.06.012
复制
发表时间：
2017-01
影响因子：
1.1
通讯作者：
Hu Shuai
中科院分区：
文献类型：
--
作者：
Li Wenjun;Feng Qilong;Chen Jianer;Hu Shuai
本文研究了参数化余路集问题、参数化路可缩性问题和参数连通支配集问题等几个参数化问题的核化算法。在简单观察的基础上，我们分别给出了核大小为4k、3k+4和O(K2)的简单核化算法，分别改进了以前的最好结果6k、5k+3和O(K3)。
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 G 7 Graphs problem. Based on simple observations, we give simple kernelization algorithms with kernel sizes 4k, 3 k+ 4, and O (k 2), respectively, which improves the previous best results 6k, 5 k+ 3, and O (k 3), respectively.
登录
查看更多内容
DOI：
10.1145/2973749
发表时间：
2009-04
期刊：
2009 50th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
H. Bodlaender;F. Fomin;D. Lokshtanov;Eelko Penninkx;Saket Saurabh;D. Thilikos
通讯作者：
H. Bodlaender;F. Fomin;D. Lokshtanov;Eelko Penninkx;Saket Saurabh;D. Thilikos
影响因子：
1.1
作者：
Venkatesh Raman;Saket Saurabh
通讯作者：
Venkatesh Raman;Saket Saurabh
线性问题核的平面图顶点划分
影响因子：
1.1
作者：
Jianxin Wang;Yongjie Yang;Jiong Guo;Jianer Chen
通讯作者：
Jianer Chen
影响因子：
1.1
作者：
Jian-xin Wang;Minzhu Xie;Jianer Chen
通讯作者：
Jian-xin Wang;Minzhu Xie;Jianer Chen
DOI：
10.1016/0022-0000(83)90012-0
发表时间：
1983-04
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
Takao Asano;T. Hirata
通讯作者：
Takao Asano;T. Hirata