A 2k-kernelization algorithm for vertex cover based on crown decomposition
A 2k-kernelization algorithm for vertex cover based on crown decomposition
复制标题
基于冠分解的2k核顶点覆盖算法
DOI：
10.1016/j.tcs.2018.05.004
复制
发表时间：
2018-08-29
影响因子：
1.1
通讯作者：
Zhu, Binhai
中科院分区：
文献类型：
--
作者：
Li, Wenjun;Zhu, Binhai
我们重新冠分解的顶点覆盖问题，给出了一个简单的2k核化算法。以前，2k核是已知的，但它是使用冠分解和线性规划计算的;此外，仅使用冠分解，只有3 k核是已知的。我们的改进冠分解具有一些额外的性质，可以用于其他相关问题。(C)2018爱思唯尔B. V.保留所有权利。
We revisit crown decomposition for the Vertex Cover problem by giving a simple 2k-kernelization algorithm. Previously, a 2k kernel was known but it was computed using both crown decomposition and linear programming; moreover, with crown decomposition alone only a 3k kernel was known. Our refined crown decomposition carries some extra property and could be used for some other related problems. (C) 2018 Elsevier B.V. All rights reserved.