We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models.
- Authors
Elkin, Michael; Zhang, Jian
- Abstract
For an unweighted undirected graph G = ( V, E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G′ = ( V, H), H ⊂ eqE, is called an (α,β)-spanner of G if for every pair of vertices u, v ∊ V, dist G′( u, v) ≤ α ⋅ dist G ( u, v) + β. It was shown in [21] that for any ∊ > 0, κ = 1,2,..., there exists an integer β = β(∊,κ) such that for every n-vertex graph G there exists a (1+∊,β)-spanner G′ with O( n 1+1/κ) edges. An efficient distributed protocol for constructing (1+∊,β)-spanners was devised in [19]. The running time and the communication complexity of that protocol are O( n 1+ρ) and O(| E| n^ρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β. In this paper we devise a protocol with a drastically improved running time ( O( n^ρ) as opposed to O( n 1+ρ)) for constructing (1+∊,β)-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 + (| E|⋅ n ρlog n)/ p) time using p processors in the EREW PRAM model. In particular, when the number of processors, p, is at least | E|⋅ n ρ, the running time of the algorithm is O(log n). We also show that our protocol for constructing (1+∊,β)-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/κ⋅ {log} n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1+∊) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O( n^ρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [23] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O( n 1+1/κ) 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. We also show that any streaming algorithm for o( n)-approximate distance computation requires Ω( n) bits of space.
- Subjects
ALGORITHMS; WRENCHES; TOOLS; MATHEMATICAL programming; MATHEMATICAL transformations; FOUNDATIONS of arithmetic; BRANCH &; bound algorithms
- Publication
Distributed Computing, 2006, Vol 18, Issue 5, p375
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-005-0147-2