Brief Announcement: Distributed Lightweight Spanner Construction for Unit Ball Graphs in Doubling Metrics
Pages 57 - 59
Abstract
Resolving an open question from 2006, we prove the existence of light-weight bounded-degree (1+ε)-spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple O(log*n)-round distributed algorithm in the LOCAL model for finding such spanners using only 2-hop neighborhood information. We further study the problem in the two dimensional Euclidean plane and we propose a construction with similar properties that has a low-intersection property as well. Lastly, we provide experimental results that confirm the performance of our algorithms.
References
[1]
Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D Tóth. 2022. Online Spanners in Metric Spaces. arXiv preprint arXiv:2202.09991 (2022).
[2]
T-H Hubert Chan and Anupam Gupta. 2009. Small hop-diameter sparse spanners for doubling metrics. Discrete & Computational Geometry 41, 1 (2009), 28--44.
[3]
Jonathan B Conroy and Csaba D Tóth. 2021. Hop-Spanners for Geometric Intersection Graphs. arXiv preprint arXiv:2112.07158 (2021).
[4]
Mirela Damian, Saurav Pandit, and Sriram Pemmaraju. 2006. Distributed spanner construction in doubling metric spaces. In International Conference on Principles of Distributed Systems. Springer, 157--171.
[5]
Michael Elkin, Arnold Filtser, and Ofer Neiman. 2020. Distributed construction of light networks. In Proceedings of the 39th Symposium on Principles of Distributed Computing. 483--492.
[6]
David Eppstein and Hadi Khodabandeh. 2021. On the Edge Crossings of the Greedy Spanner. In 37th International Symposium on Computational Geometry, Vol. 12. 37.
[7]
David Eppstein and Hadi Khodabandeh. 2021. Optimal Spanners for Unit Ball Graphs in Doubling Metrics. arXiv preprint arXiv:2106.15234 (2021).
[8]
Arnold Filtser and Shay Solomon. 2016. The greedy spanner is existentially optimal. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing. 9--17.
[9]
Jie Gao, Leonidas J Guibas, John Hershberger, Li Zhang, and An Zhu. 2005. Geometric spanners for routing in mobile networks. IEEE journal on selected areas in communications 23, 1 (2005), 174--185.
[10]
Joachim Gudmundsson, Christos Levcopoulos, and Giri Narasimhan. 2002. Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31, 5 (2002), 1479--1500.
[11]
Iyad A Kanj, Ljubomir Perkovic, and Ge Xia. 2008. Computing lightweight spanners locally. In International Symposium on Distributed Computing. Springer, 365--378.
[12]
Giri Narasimhan and Michiel Smid. 2007. Geometric spanner networks. Cambridge University Press.
[13]
David Peleg and Liam Roditty. 2010. Localized spanner construction for ad hoc networks with variable transmission range. ACM Transactions on Sensor Networks (TOSN) 7, 3 (2010), 1--14.
[14]
Johannes Schneider and Roger Wattenhofer. 2008. A log-star distributed maximal independent set algorithm for growth-bounded graphs. In Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing. 35--44.
Index Terms
- Brief Announcement: Distributed Lightweight Spanner Construction for Unit Ball Graphs in Doubling Metrics
Recommendations
On Hierarchical Routing in Doubling Metrics
We study the problem of routing in doubling metrics and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with a small amount of routing information stored at each vertex). We say that a metric (...
Small Hop-diameter Sparse Spanners for Doubling Metrics
Given a metric M=(V,d), a graph G=(V,E) is a t-spanner for M if every pair of nodes in V has a "short" path (i.e., of length at most t times their actual distance) between them in the spanner. Furthermore, this spanner has a hop diameter bounded by D if ...
New Doubling Spanners
In a seminal STOC 1995 paper, Arya et al. conjectured that spanners for low-dimensional Euclidean spaces with constant maximum degree, hop-diameter $O(\log n)$, and lightness $O(\log n)$ (i.e., weight $O(\log n) \cdot w({MST}))$ can be constructed in $O(n ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
464 pages
ISBN:9781450391467
DOI:10.1145/3490148
- General Chair:
- Kunal Agrawal,
- Program Chair:
- I-Ting Angelina Lee
Copyright © 2022 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
- SIGARCH: ACM Special Interest Group on Computer Architecture
- EATCS: European Association for Theoretical Computer Science
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 July 2022
Check for updates
Author Tags
Qualifiers
- Extended-abstract
Conference
SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures
July 11 - 14, 2022
PA, Philadelphia, USA
Acceptance Rates
Overall Acceptance Rate 447 of 1,461 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 74Total Downloads
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)1
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in