Fully Dynamic Maintenance of Vertex Cover
Fully Dynamic Maintenance of Vertex Cover
复制标题
顶点覆盖的全动态维护
DOI：
10.1007/3-540-57899-4_44
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
E. Lloyd
中科院分区：
文献类型：
--
作者：
Z. Ivkovic;E. Lloyd
研究了在边可以动态插入和删除的情况下维护顶点覆盖近似解的问题。我们提出了一种完全动态算法\(A1\)，它以分摊的方式有效地适应这种变化。我们进一步对该方法进行了推广，并提出了一族算法\(A_{k}\)，\(k > -1\)。每次插入/删除操作时，每个\(A_{k}\)的分摊运行时间为\(\Theta ((\upsilon + e)\frac{1 + \sqrt{1 + 4(k + 1)(2k + 3)}}{2(2k + 3)})\)，其中\(e\)表示操作开始时图\(G\)的边数。由此可知，这种分摊运行时间可以任意接近\(\Theta ((\upsilon + e)\frac{\sqrt{2}}{2})\)。这里给出的每个算法都具有\(2\) - 竞争力，从而与现有的最佳离线顶点覆盖近似算法的竞争比相匹配。
The problem of maintaining an approximate solution for vertex cover when edges may be inserted and deleted dynamically is studied. We present a fully dynamic algorithm A1 that, in an amortized fashion, efficiently accommodates such changes. We further provide for a generalization of this method and present a family of algorithms A k , k >−1. The amortized running time of each A k is \(\Theta ((\upsilon + e)\tfrac{{1 + \sqrt {1 + 4(k + 1)(2k + 3)} }}{{2(2k + 3)}})\) per Insert/Delete operation, where e denotes the number of edges of the graph G at the time that the operation is initiated. It follows that this amortized running time may be made arbitrarily close to \(\Theta ((\upsilon + e)\tfrac{{\sqrt 2 }}{2})\). Each of the algorithms given here is 2-competitive, thereby matching the competitive ratio of the best existing off-line approximation algorithms for vertex cover.