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. A path has stretch t if its weight is at most t times the distance between its end points. We consider a weighted undirected graph G=(V, E) and present algorithms that compute paths with stretch 2⩽t⩽log n. We present a O˜((m+k)n^(2+ε/t)) time randomized algorithm that finds paths between k specified pairs of vertices and a O˜((m+ns)n^{2(1+log(n) m+ε)}t/) deterministic algorithm that finds paths from s specified sources to all other vertices (for any fixed ε>0), where n=|V| and m=|E|. This improves significantly over the slower O˜(min{k, n}m) exact shortest paths algorithms and a previous O˜(mn⁶⁴t/+kn ³²t/) time algorithm by Awerbuch et al. 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˜(n^1+(2+ε/t)) in O˜(mn^(2+ε/t)) expected time (for any fixed ε>0), what constitutes a faster construction (by a factor of n⁽³⁺²/t)) of sparser spanners than was previously attainable. We also provide efficient parallel constructions. Our algorithms are based on new structures called pairwise-covers and a novel approach to construct them efficiently