Book chapter
Distributed Spanner Construction in Doubling Metric Spaces
Principles of Distributed Systems, pp.157-171
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2006
DOI: 10.1007/11945529_12
Abstract
This paper presents a distributed algorithm that runs on an n-node unit ball graph (UBG) G residing in a metric space of constant doubling dimension, and constructs, for any ε> 0, a (1 + ε)-spanner H of G with maximum degree bounded above by a constant. In addition, we show that H is “lightweight”, in the following sense. Let Δ denote the aspect ratio of G, that is, the ratio of the length of a longest edge in G to the length of a shortest edge in G. The total weight of H is bounded above by O(logΔ) · wt(MST), where MST denotes a minimum spanning tree of the metric space. Finally, we show that H satisfies the so called leapfrog property, an immediate implication being that, for the special case of Euclidean metric spaces with fixed dimension, the weight of H is bounded above by O(wt(MST)). Thus, the current result subsumes the results of the authors in PODC 2006 that apply to Euclidean metric spaces, and extends these results to metric spaces with constant doubling dimension.
Details
- Title: Subtitle
- Distributed Spanner Construction in Doubling Metric Spaces
- Creators
- Mirela Damian - Villanova UniversitySaurav Pandit - University of IowaSriram Pemmaraju - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Principles of Distributed Systems, pp.157-171
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/11945529_12
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2006
- Academic Unit
- Computer Science
- Record Identifier
- 9984259490002771
Metrics
2 Record Views