Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
复制标题
DOI：
10.1145/320211.320215
复制
发表时间：
1999-07
期刊：
影响因子：
--
通讯作者：
Monika Henzinger;Valerie King
中科院分区：
文献类型：
--
作者：
Monika Henzinger;Valerie King
本文在完全动态的算法中解决了一个长期的开放问题：我们介绍了第一个完全动态的算法，该算法在每段边缘插入或删除算法中保持连通性，两场和近似的最小跨越树。新型的图形分解是使用简单的数据结构并具有较小的常数因素的Las-Vegas型随机算法。 M0是初始图中的边缘数，P更新的预期时间为O（P Log3 N）（在整个论文中，对数是基于2）的连接性和两次查询时间。 log n/log n）。 IS O（QK log3 n）。 P更新中的最小生成树的最小生成树的近似（（P log3 n logu）/ε），其中边缘的权重在1和U之间。
This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor. Let n denote the number of nodes in the graph. For a sequence of &OHgr;(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is O(p log3 n) (througout the paper the logarithms are based 2) for connectivity and bipartiteness. The worst-case time for one query is O(log n/log log n). For the k-edge witness problem (“Does the removal of k given edges disconnect the graph?”) the expected time for p updates is O(p log3 n) and the expected time for q queries is O(qk log3 n). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O(pk log3 n). This implies an algorithm to maintain a 1 + ε-approximation of the minimum spanning tree in expected time O((p log3 n logU)/ε) for p updates, where the weights of the edges are between 1 and U.