Planar graph vertex partition for linear problem kernels
Planar graph vertex partition for linear problem kernels
复制标题
线性问题核的平面图顶点划分
DOI：
10.1016/j.jcss.2012.08.001
复制
发表时间：
2013-08
影响因子：
1.1
通讯作者：
Jianer Chen
中科院分区：
文献类型：
--
作者：
Jianxin Wang;Yongjie Yang;Jiong Guo;Jianer Chen
对于平面图中的顶点和边与解的距离很小的问题，引入了一种简单的顶点集划分方法来分析核。这种方法直接导致改进的内核大小的几个问题，而不需要新的约简规则。此外，针对连通顶点覆盖、边支配集和最大三角形填充问题，提出了新的核化算法，进一步提高了这些问题的核大小。
A simple partition of the vertex set of a graph is introduced to analyze kernels for planar graph problems in which vertices and edges not in a solution have small distance to the solution. This method directly leads to improved kernel sizes for several problems, without needing new reduction rules. Moreover, new kernelization algorithms are developed for Connected Vertex Cover, Edge Dominating Set, and Maximum Triangle Packing problems, further improving the kernel sizes for these problems.
登录
查看更多内容
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
DOI：
10.1007/978-3-642-02927-1_32
发表时间：
2009-07
期刊：
--
影响因子：
--
作者：
M. Dom;D. Lokshtanov;Saket Saurabh
通讯作者：
M. Dom;D. Lokshtanov;Saket Saurabh
DOI：
10.2307/3616070
发表时间：
1973-12
期刊：
The Mathematical Gazette
影响因子：
--
作者：
K. Fraughnaugh
通讯作者：
K. Fraughnaugh
DOI：
10.1007/978-3-8348-9329-1_2
发表时间：
2010
期刊：
--
影响因子：
--
作者：
M. Loebl
通讯作者：
M. Loebl
DOI：
10.1016/j.dam.2008.07.011
发表时间：
2009-02
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Hannes Moser;S. Sikdar
通讯作者：
Hannes Moser;S. Sikdar