Maintaining a large matching and a small vertex cover
Maintaining a large matching and a small vertex cover
复制标题
维持大匹配和小顶点覆盖
DOI：
10.1145/1806689.1806753
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
R. Rubinfeld
中科院分区：
文献类型：
--
作者：
Krzysztof Onak;R. Rubinfeld
我们考虑在动态变化的图中维护较大匹配和小顶点盖的问题。图表的每个更新都是边删除或边缘插入。我们给出了第一个随机数据结构，该数据结构同时达到了恒定的近似因子，并处理k*polylog（n）时间中的k更新序列，其中n是图中的顶点的数量。以前的数据结构需要每次更新多项式计算。
We consider the problem of maintaining a large matching and a small vertex cover in a dynamically changing graph. Each update to the graph is either an edge deletion or an edge insertion. We give the first randomized data structure that simultaneously achieves a constant approximation factor and handles a sequence of K updates in K*polylog(n) time, where n is the number of vertices in the graph. Previous data structures require a polynomial amount of computation per update.