Efficient algorithms for constructing (1+epsilon,beta)-spanners in the distributed and streaming models
For an unweighted undirected graph G = (V, E), and a pair of positive integers alpha >= 1, beta >= 0, a subgraph G' = (V, H), H subset of E, is called an (alpha, beta)-spanner of G if for every pair of vertices u, v is an element of V, dist(G')(u, v)   0, K = 1, 2..., there exists an integer beta = beta(is an element of, K) such that for every n-vertex graph G there exists a (1 + is an element of, beta)-spanner G' with O(n(1+1/K)) edges. An efficient distributed protocol for constructing (1 + is an element of, beta)-spanners was devised in [19]. The running time and the communication complexity of that protocol are O(n(1+rho)) and O(vertical bar E vertical bar n(rho)), respectively, where rho is an additional control parameter of the protocol that affects only the additive term beta. In this paper we devise a protocol with a drastically improved running time (O(n(rho)) as opposed to O(n(1+rho))) for constructing (1 + is an element of, beta)-spanners. Our protocol has the same communication complexity as the protocol of [19], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [19]. The protocol can be easily extended to a parallel implementation which runs in O(log n + (vertical bar E vertical bar (.) n(rho)logn)/p) time using p processors in the EREW PRAM model. In particular, when the number of processors, p, is at least vertical bar E vertical bar center dot n(rho), the running time of the algorithm is 0 (log n). We also show that our protocol for constructing (1 + is an element of, beta) -spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n(1+1/K) center dot log n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1 + is an element of) and an additive term of greater than the shortest paths. Our algorithm processes each edge in time O(n(rho)), for an arbitrarily small p > 0. The only previously known algorithm for the problem [23] constructs paths of length K times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n(1+1/K)) time for processing each edge of the input graph. However, the algorithm of [23] uses just one pass over the input, as opposed to the constant number of passes in our algorithm.(1) We also show that any streaming algorithm for o(n)approximate distance computation requires Omega (n) bits of space.
streaming model spanner almost shortest paths