All pairs almost shortest paths
All pairs almost shortest paths
复制标题
所有对几乎最短路径
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Uri Zwick
中科院分区：
文献类型：
--
作者：
D. Dor;S. Halperin;Uri Zwick
设G=（V，E）是一个n阶无向赋权图.一个简单的论证表明，计算G中的所有距离，其加性单侧误差最多为1，与布尔矩阵乘法一样困难。在D. Aingworth et al.（1996），我们描述了一个O/spl波浪号/（min{n/sup 3/2/m/sup 1/2/，n/sup 7/3/}）时间算法APASP/sub 2/，用于计算G中的所有距离，其加性单侧误差至多为2。算法APASP/sub 2/简单，易于实现，比已知的最快矩阵乘法算法更快。此外，对于任意偶数k>2，我们给出了计算G中所有距离的O/spl代/（min{n/sup 2-（2）/（k +2）/m/sup（2）/（k+2）/，n/sup 2+（2）/（3 k-2）/}）时间算法APASP/sub k/，其加性单侧误差至多为k.我们还给出了一个O/spl波浪号/（n/sup 2/）时间算法APASP/sub /spl infin//，用于在n个顶点的无权无向图中产生stretch 3估计距离.以前在O/spl代字号/（n/sup 2/）时间中没有获得恒定的拉伸因子。我们说加权图F=（V，E '）k-模拟未加权图G=（V，E），如果对于每个u，v/spl isin/V我们有/spl delta//sub G/（u，v）/spl les//spl delta//sub F/（u，v）/spl les//spl delta//sub G/（u，v）+k。我们证明了每个n阶无权图都有一个边数为O/spl/（n/sup 3/2/）的2-模拟器和一个边数为O/spl/（n/sup 4/3/）的4-模拟器.这些结果是渐近紧的。最后，我们证明了任何n个顶点上的加权无向图都有一个3-边数为O/spl波浪号/（n/sup 3/2/）的图，并且这样的3-边数可以在O/spl波浪号/（mn/sup 1/2/）时间内建立。我们还描述了一个O/spl波浪号/（n（m/sup 2/3/+n））时间算法估计所有的距离在一个加权无向图的n个顶点的拉伸因子最多为3。
Let G=(V,E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of D. Aingworth et al. (1996), we describe an O/spl tilde/(min{n/sup 3/2/m/sup 1/2/,n/sup 7/3/}) time algorithm APASP/sub 2/ for computing all distances in G with an additive one-sided error of at most 2. The algorithm APASP/sub 2/ is simple, easy to implement, and faster than the fastest known matrix multiplication algorithm. Furthermore, for every even k>2, we describe an O/spl tilde/(min{n/sup 2-(2)/(k+2)/m/sup (2)/(k+2)/, n/sup 2+(2)/(3k-2)/}) time algorithm APASP/sub k/ for computing all distances in G with an additive one-sided error of at most k. We also give an O/spl tilde/(n/sup 2/) time algorithm APASP/sub /spl infin// for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in O/spl tilde/(n/sup 2/) time. We say that a weighted graph F=(V,E') k-emulates an unweighted graph G=(V,E) if for every u, v/spl isin/V we have /spl delta//sub G/(u,v)/spl les//spl delta//sub F/(u,v)/spl les//spl delta//sub G/(u,v)+k. We show that every unweighted graph on n vertices has a 2-emulator with O/spl tilde/(n/sup 3/2/) edges and a 4-emulator with O/spl tilde/(n/sup 4/3/) edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with O/spl tilde/(n/sup 3/2/) edges and that such a 3-spanner can be built in O/spl tilde/(mn/sup 1/2/) time. We also describe an O/spl tilde/(n(m/sup 2/3/+n)) time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3.