Faster Approximation of Distances in Graphs
Faster Approximation of Distances in Graphs
复制标题
更快地近似图中的距离
DOI：
10.1007/978-3-540-73951-7_47
复制
发表时间：
2007
期刊：
影响因子：
1.1
通讯作者：
S. Kasiviswanathan
中科院分区：
文献类型：
--
作者：
P. Berman;S. Kasiviswanathan
设G =（V，E）是n个顶点m条边的加权无向图，dG是它的最短路度量.本文提出了两个简单的确定性算法来逼近G中的所有对最短路。我们的第一个算法运行时间为O（n2），并且对于任何u，v ∈ V，报告的距离不大于2dG（u，v）+ h（u，v）。这里，h（u，v）是u和v之间最短路径上的最大边权重。由于Baswana和Kavitha实现了相同结果，因此之前的算法是随机的。我们的第二个算法的所有对最短路径问题使用布尔矩阵乘法和任何u，v ∈ V报告的距离不大于（1 + e）dG（u，v）+2h（u，v）。目前最著名的布尔矩阵乘法算法产生一个O（n2.24+o（1）e-3 log（ne-1））的时间限制为这个算法。以前最著名的结果埃尔金与类似的乘法因子有一个更大的附加误差项。
我们还考虑了图的直径和半径的近似。对于半径估计问题，我们给出了一个近似3/2的算法，其时间复杂度为O（m <$n + n2）. Aingworth，Chekuri，Indyk和Motwani使用了类似的方法，并获得了类似的直径近似问题的结果。此外，我们表明，如果图有一个小的分离器分解的3/2近似的直径和半径可以更有效地获得。
Let G = (V,E) be a weighted undirected graph on n vertices and m edges, and let dG be its shortest path metric. We present two simple deterministic algorithms for approximating all-pairs shortest paths in G. Our first algorithm runs in O (n2 time, and for any u, v ∈ V reports distance no greater than 2dG(u, v) + h(u, v). Here, h(u, v) is the largest edge weight on a shortest path between u and v. The previous algorithm, due to Baswana and Kavitha that achieved the same result was randomized. Our second algorithm for the all-pairs shortest path problem uses Boolean matrix multiplications and for any u, v ∈ V reports distance no greater than (1 + e)dG(u, v) + 2h(u, v). The currently best known algorithm for Boolean matrix multiplication yields an O(n2.24+o(1)e-3 log(ne-1)) time bound for this algorithm. The previously best known result of Elkin with a similar multiplicative factor had a much bigger additive error term.
We also consider approximating the diameter and the radius of a graph. For the problem of estimating the radius, we present an almost 3/2-approximation algorithm which runs in O(m √n + n2) time. Aingworth, Chekuri, Indyk, and Motwani used a similar approach and obtained analogous results for the diameter approximation problem. Additionally, we show that if the graph has a small separator decomposition a 3/2-approximation of both the diameter and the radius can be obtained more efficiently.