A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n1+1/k) Size in Weighted Graphs
A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n1+1/k) Size in Weighted Graphs
复制标题
计算加权图中 O(n1 1/k) 大小的 (2k-1)-Spanner 的简单线性时间算法
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Sandeep Sen
中科院分区：
文献类型：
--
作者：
Surender Baswana;Sandeep Sen
设\(G(V, E)\)是一个无向加权图，其中\(\vert V\vert = n\)，\(\vert E\vert = m\)。图\(G(V, E)\)的一个\(t\)-生成树是一个子图\(G(V, E_S)\)，使得生成树中任意一对顶点之间的距离至多是给定图中两者距离的\(t\)倍。1963年埃尔德什（Erdos）的围长猜想意味着，对于任何\((2k - 1)\)-生成树，在最坏情况下需要\(\Omega(n^{1 + 1/k})\)条边，这已在\(k = 1, 2, 3, 5\)时得到证明。存在多项式时间算法，能够构建出大小符合此猜想下界的生成树，并且已知的最佳算法的期望运行时间为\(O(mn^{1/k})\)。在本文中，我们提出一种极其简单的线性时间随机算法，该算法构建出大小符合猜想下界的\((2k - 1)\)-生成树。
我们的算法在计算生成树时仅需局部信息，因此可适当调整以获得高效的分布式和并行算法。
Let G(V, E) be an undirected weighted graph with |V| = n, and |E| = m. A t-spanner of the graph G(V, E) is a sub-graph G(V, ES) such that the distance between any pair of vertices in the spanner is at most t times the distance between the two in the given graph. A 1963 girth conjecture of Erdos implies that Ω(n1+1/k) edges are required in the worst case for any (2k - 1)-spanner, which has been proved for k = 1, 2, 3, 5. There exist polynomial time algorithms that can construct spanners with the size that matches this conjectured lower bound, and the best known algorithm takes O(mn1/k) expected running time. In this paper, we present an extremely simple linear time randomized algorithm that constructs (2k - 1)-spanner of size matching the conjectured lower bound.
Our algorithm requires local information for computing a spanner, and thus can be adapted suitably to obtain efficient distributed and parallel algorithms.