A Simple Linear Time Algorithm for Computing a (2k — 1)-Spanner of O(n 1+1/k ) Size in Weighted Graphs

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,E_S) 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 Erdős 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.