Fast algorithms for constructing t-spanners and paths with stretch t

The distance between two vertices in a weighted graph is the weight of a minimum-weight path between them (where the weight of a path is the sum of the weights of the edges in the path). A path has stretch t if its weight is at most t times the distance between its end points. We present algorithms that compute paths of stretch 2 less than or equal to t less than or equal to log n on undirected graphs G = (V, E) epsilon' > 0 is at least as large as some fixed epsilon > 0. We present an (O) over tilde((m + k)n((2+epsilon)/t)) time randomized algorithm that finds paths between k specified pairs of vertices and an (O) over tilde((m + ns)n(2(1+log n m+epsilon/t)) deterministic algorithm that finds paths from s specified sources to all other vertices (for any fixed epsilon > 0), where n = \V\ and m = \E\. This improves significantly over the slower (O) over tilde(min{k, n}m) exact shortest paths algorithms and a previous (O) over tilde(mn(64/t) + kn(32/t)) time algorithm by Awerbuch et al. [Proc. 34th IEEE Annual Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 1993, pp. 638-647]. A t-spanner of a graph G is a set of weighted edges on the vertices of G such that distances in the spanner are not smaller and within a factor of t from the corresponding distances in G. Previous work was concerned with bounding the size and efficiently constructing t-spanners. We construct t-spanners of size (O) over tilde(n(1+(2+epsilon))/t in (O) over tilde(mn((2+epsilon)/t)) expected time (for any fixed epsilon > 0), which constitutes a faster construction (by a factor of n(3+2/t)/m) of sparser spanners than was previously attainable. We also provide efficient parallel constructions. Our algorithms are based on pairwise covers and a novel approach to construct them efficiently.