Improved upper bounds for vertex cover
Improved upper bounds for vertex cover
复制标题
DOI：
10.1016/j.tcs.2010.06.026
复制
发表时间：
2010-09-06
影响因子：
1.1
通讯作者：
Xia, Ge
中科院分区：
文献类型：
--
作者：
Chen, Jianer;Kanj, Iyad A.;Xia, Ge
本文提出了一种O（1.2738(k) + kn）时间多项式空间算法，改进了先前Chen、Kanj和Jia的O（1.286(k) + kn）时间多项式空间上界。以前的大多数算法都依赖于详尽的逐案分支规则，以及一个潜在的保守的最坏情况假设。本文的贡献在于所提出的算法的简单性、一致性和遗忘性。介绍了几种新技术，以及对以前技术的推广，包括：一般折叠、构造、元组和局部平摊分析。该算法还改进了Chandran和Grandoni问题的O(1.2745（k)k(4) + kn）时间指数空间上界。(C) 2010 Elsevier B.V.版权所有
This paper presents an O(1.2738(k) + kn)-time polynomial-space algorithm for VERTEX COVER improving the previous O(1.286(k) + kn)-time polynomial-space upper bound by Chen, Kanj, and Jia. Most of the previous algorithms rely on exhaustive case-by-case branching rules, and an underlying conservative worst-case-scenario assumption. The contribution of the paper lies in the simplicity, uniformity, and obliviousness of the algorithm presented. Several new techniques, as well as generalizations of previous techniques, are introduced including: general folding, struction, tuples, and local amortized analysis. The algorithm also improves the O(1.2745(k)k(4) + kn)-time exponential-space upper bound for the problem by Chandran and Grandoni. (C) 2010 Elsevier B.V. All rights reserved.