Dynamic approximate all-pairs shortest paths in undirected graphs
Dynamic approximate all-pairs shortest paths in undirected graphs
复制标题
无向图中动态近似全对最短路径
DOI：
10.1137/090776573
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Uri Zwick
中科院分区：
文献类型：
--
作者：
L. Roditty;Uri Zwick
我们在未加权的未方向图中获得了三种近似全对路径问题的三种动态算法：1）对于任何固定 / spl epsiv /> 0，一种降低算法，其预期的总运行时间是O（Mn），其中m是M是边缘和n的数量是初始图中的顶点数。每个距离查询都在O（1）最差的时间时间回答，并且返回距离的拉伸最多为1 + /Spl Epsiv /。该算法使用O（N/SUP 2/）空间； 2）对于任何固定的整数K / SPL GES / 1，一种预期总运行时间为O（MN）的减少算法。每个查询都在O（1）最差的时间时间回答，并且返回距离的拉伸最多为2K -1。此算法仅使用O（M + N/SUP 1 + 1 + 1/K/）空间。它是通过动态的Thorup和Zwick的动态技术获得的。除了提高空间效率外，该算法也是用于获得第一个算法的构件之一。 3）对于任何固定/spl epsiv/，/spl delta/> 0以及每个t/spl les/m/sup 1/2-/spl delta //，一种完全动态的算法，具有预期的摊销更新时间（MN） /t）和最差的查询时间O（t）。返回距离的拉伸最多为1+/spl epsiv/。也可以使所有算法都可以处理具有小整数边缘重量的无向图。如果最大的边缘重量为b，则运行时间上的所有边界都乘以b。
We obtain three dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs: 1) For any fixed /spl epsiv/ > 0, a decremental algorithm with an expected total running time of O(mn), where m is the number of edges and n is the number of vertices in the initial graph. Each distance query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 1 + /spl epsiv/. The algorithm uses O(n/sup 2/) space; 2) For any fixed integer k /spl ges/ 1, a decremental algorithm with an expected total running time of O(mn). Each query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 2k - 1. This algorithm uses, however, only O(m + n/sup 1+1/k/) space. It is obtained by dynamizing techniques of Thorup and Zwick. In addition to being more space efficient, this algorithm is also one of the building blocks used to obtain the first algorithm; 3) For any fixed /spl epsiv/, /spl delta/ > 0 and every t /spl les/ m/sup 1/2-/spl delta//, a fully dynamic algorithm with an expected amortized update time of O(mn/t) and worst-case query time of O(t). The stretch of the returned distances is at most 1+/spl epsiv/. All algorithms can also be made to work on undirected graphs with small integer edge weights. If the largest edge weight is b, then all bounds on the running times are multiplied by b.