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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Awerbuch, B., Goldberg, A., Luby, M., Plotkin, S.: Network decomposition and locality in distributed computation. In: IEEE Symposium on Foundations of Computer Science, pp. 364–369 (1989)
Chan, H.T.-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: SODA 2005: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 762–771 (2005)
Hubert Chan, T.-H.: Personal Communication (2006)
Chan, T.-H.H., Gupta, A.: Small hop-diameter sparse spanners for doubling metrics. In: SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 70–78 (2006)
Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. Discrete & Computational Geometry 32(2), 207–230 (2004)
Damian, M., Pandit, S., Pemmaraju, S.: Local approximation schemes for topology control. In: PODC 2006: Proceedings of the twenty-fifth annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (2006)
Das, G., Heffernan, P., Narasimhan, G.: Optimally sparse spanners in 3-dimensional euclidean space. In: ACM Symposium on Computational Geometry, pp. 53–62 (1993)
Das, G., Narasimhan, G.: A fast algorithm for constructing sparse euclidean spanners. Int. J. Comput. Geometry Appl. 7(4), 297–315 (1997)
Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31(5), 1479–1500 (2002)
Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics, and their applications. In: SCG 2005: Proceedings of the 21st annual symposium on Computational geometry, pp. 150–158 (2005)
Krauthgamer, R., Gupta, A., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: FOCS 2003: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 534–543 (2003)
Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: SODA 2004: Proceedings of the 15th annual ACM-SIAM symposium on Discrete algorithms, pp. 798–807 (2004)
Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: PODC 2005: Proceedings of the twenty-fourth annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pp. 60–68 (2005)
Li, X.-Y., Wang, Y.: Efficient construction of low weighted bounded degree planar spanner. International Journal of Computational Geometry and Applications 14(1–2), 69–84 (2004)
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)
Rajaraman, R.: Topology control and routing in ad hoc networks: A survey. SIGACT News 33, 60–73 (2002)
Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: STOC 2004: Proceedings of the 36th annual ACM symposium on Theory of computing, pp. 281–290 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damian, M., Pandit, S., Pemmaraju, S. (2006). Distributed Spanner Construction in Doubling Metric Spaces. In: Shvartsman, M.M.A.A. (eds) Principles of Distributed Systems. OPODIS 2006. Lecture Notes in Computer Science, vol 4305. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11945529_12
Download citation
DOI: https://doi.org/10.1007/11945529_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49990-9
Online ISBN: 978-3-540-49991-6
eBook Packages: Computer ScienceComputer Science (R0)