Simplicity is Beauty: Improved Upper Bounds for Vertex Cover
Simplicity is Beauty: Improved Upper Bounds for Vertex Cover
复制标题
简单就是美：改进顶点覆盖的上限
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Ge Xia
中科院分区：
文献类型：
--
作者：
Jianer Chen;Iyad A. Kanj y;Ge Xia
(cid:151)本文提出了 V ERTEX COVER 的 O (1 : 2738 k + kn ) 时间多项式空间算法，改进了 Chen、Kanj 和 Jia 之前的 O (1 : 286 k + kn ) 时间多项式空间算法，以及 Chandran 最新的 O (1 : 2745 k k 4 + kn ) 时间指数空间算法 和格兰多尼。以前的大多数算法都依赖于详尽的案例分析以及潜在的保守的最坏情况假设。这篇论文的贡献在于所提出的算法的极端简单性、统一性和遗忘性。介绍了几种新技术以及先前技术的概括，包括：一般折叠、结构、元组和局部摊销分析。该算法还改进了度数为 6 的图上的独立集问题的上限。
(cid:151)This paper presents an O (1 : 2738 k + kn ) -time polynomial-space algorithm for V ERTEX C OVER improving both the previous O (1 : 286 k + kn ) -time polynomial-space algorithm by Chen, Kanj, and Jia, and the very recent O (1 : 2745 k k 4 + kn ) - time exponential-space algorithm, by Chandran and Grandoni. Most of the previous algorithms rely on exhaustive case-by-case analysis, and an underlying conservative worst-case-scenario assumption. The contribution of the paper lies in the extreme 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 induces improvement on the upper bound for the I NDEPENDENT S ET problem on graphs of degree bounded by 6.