Randomized dynamic graph algorithms with polylogarithmic time per operation
Randomized dynamic graph algorithms with polylogarithmic time per operation
复制标题
每次操作具有多对数时间的随机动态图算法
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Valerie King
中科院分区：
文献类型：
--
作者：
Monika Henzinger;Valerie King
本文解决了一个长期开放的问题，在全动态算法：我们提出了第一个全动态算法，保持连通性，二分性，并近似最小生成树在多对数时间每边插入或删除。该算法的设计使用一种新的动态技术，结合了一种新的图分解与随机化。它们是Las-Vegas型随机算法，使用简单的数据结构，具有小的常数因子。设n表示图中的节点数。对于一个V（m0）操作序列，其中m0是初始图中的边数，p次更新的预期时间是O（p log 3 n）（在整个论文中，算法都是以2为底）。连通性和二分性。时间复杂度为O（log n/log log n）。对于k边见证问题（“移除k条给定边是否会断开图？）p次更新的预期时间是O（p log 3 n），q次查询的预期时间是O（qk log 3 n）。给定一个具有k个不同权重的图，最小生成树可以在预期时间O（pk log 3 n）内在p次更新的序列期间保持。这意味着对于p次更新，在预期时间O（（p log 3 n log U）/e）内保持最小生成树的11 e近似的算法，其中边的权重在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 V(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is O( p log 3 n) (Throughout the paper the logarithms are base 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 log 3 n) and the expected time for q queries is O(qk log 3 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 log 3 n). This implies an algorithm to maintain a 1 1 e-approximation of the minimum spanning tree in expected time O((p log 3 n log U)/e) for p updates, where the weights of the edges are between 1 and U.