Document Open Access Logo

Distributed Construction of Lightweight Spanners for Unit Ball Graphs

Authors David Eppstein, Hadi Khodabandeh

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.21.pdf
  • Filesize: 0.85 MB
  • 23 pages

Document Identifiers

Author Details

David Eppstein
  • Department of Computer Science, University of California, Irvine, CA, USA
Hadi Khodabandeh
  • Department of Computer Science, University of California, Irvine, CA, USA

Cite As Get BibTex

David Eppstein and Hadi Khodabandeh. Distributed Construction of Lightweight Spanners for Unit Ball Graphs. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.DISC.2022.21

Abstract

Resolving an open question from 2006 [Damian et al., 2006], we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple 𝒪(log^*n)-round distributed algorithm in the LOCAL model of computation, that given a unit ball graph G with n vertices and a positive constant ε < 1 finds a (1+ε)-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the best prior lightness bound, the algorithm of Damian, Pandit, and Pemmaraju [Damian et al., 2006], which runs in 𝒪(log^*n) rounds in the LOCAL model, but has a 𝒪(log Δ) bound on its lightness, where Δ is the ratio of the length of the longest edge to the length of the shortest edge in the unit ball graph. Next, we adjust our algorithm to work in the CONGEST model, without changing its round complexity, hence proposing the first spanner construction for unit ball graphs in the CONGEST model of computation. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersections per node. Lastly, we provide experimental results that confirm our theoretical bounds, and show an efficient performance from our distributed algorithm compared to the best known centralized construction.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Sparsification and spanners
  • Networks → Network control algorithms
Keywords
  • spanners
  • doubling metrics
  • distributed
  • topology control

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mohammad Ali Abam, Mark De Berg, Mohammad Farshi, and Joachim Gudmundsson. Region-fault tolerant geometric spanners. Discrete & Computational Geometry, 41(4):556-582, 2009. URL: https://doi.org/10.1007/s00454-009-9137-7.
  2. Ingo Althöfer, Gautam Das, David Dobkin, and Deborah Joseph. Generating sparse spanners for weighted graphs. In John R. Gilbert and Rolf Karlsson, editors, Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT), volume 447 of Lecture Notes in Computer Science, pages 26-37. Springer, 1990. URL: https://doi.org/10.1007/3-540-52846-6_75.
  3. Khaled Alzoubi, Xiang-Yang Li, Yu Wang, Peng-Jun Wan, and Ophir Frieder. Geometric spanners for wireless ad hoc networks. IEEE Transactions on Parallel and Distributed Systems, 14(4):408-421, 2003. URL: https://doi.org/10.1109/TPDS.2003.1195412.
  4. Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Near-linear time construction of sparse neighborhood covers. SIAM Journal on Computing, 28(1):263-277, 1998. URL: https://doi.org/10.1137/S0097539794271898.
  5. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (α,β)-spanners. ACM Transactions on Algorithms, 7(1):5, 2010. URL: https://doi.org/10.1145/1868237.1868242.
  6. Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D Tóth. Online spanners in metric spaces. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.09991.
  7. Glencora Borradaile, Hung Le, and Christian Wulff-Nilsen. Greedy spanners are optimal in doubling metrics. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2371-2379. Society for Industrial and Applied Mathematics, 2019. URL: https://doi.org/10.1137/1.9781611975482.145.
  8. Rebecca Braynard, Dejan Kostic, Adolfo Rodriguez, Jeffrey Chase, and Amin Vahdat. Opus: an overlay peer utility service. In Proceedings of the 5th IEEE Conference on Open Architectures and Network Programming (OPENARCH), pages 167-178. IEEE, 2002. URL: https://doi.org/10.1109/OPNARC.2002.1019237.
  9. T-H Hubert Chan and Anupam Gupta. Small hop-diameter sparse spanners for doubling metrics. Discrete & Computational Geometry, 41(1):28-44, 2009. Google Scholar
  10. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault tolerant spanners for general graphs. SIAM Journal on Computing, 39(7):3403-3423, 2010. URL: https://doi.org/10.1137/090758039.
  11. Paul Chew. There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences, 39(2):205-219, 1989. URL: https://doi.org/10.1016/0022-0000(89)90044-5.
  12. Edith Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing, 28(1):210-236, 1998. URL: https://doi.org/10.1137/S0097539794261295.
  13. Mirela Damian, Saurav Pandit, and Sriram Pemmaraju. Distributed spanner construction in doubling metric spaces. In International Conference on Principles of Distributed Systems, pages 157-171. Springer, 2006. Google Scholar
  14. Mirela Damian, Saurav Pandit, and Sriram Pemmaraju. Local approximation schemes for topology control. In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 208-217, 2006. Google Scholar
  15. Gautam Das. The visibility graph contains a bounded-degree spanner. In Proceedings of the 9th Canadian Conference on Computational Geometry (CCCG), pages 70-75, 1997. URL: https://cccg.ca/proceedings/1997/.
  16. Andrew Dobson and Kostas E. Bekris. Sparse roadmap spanners for asymptotically near-optimal motion planning. International Journal of Robotics Research, 33(1):18-47, 2014. URL: https://doi.org/10.1177/0278364913498292.
  17. Michael Elkin. Computing almost shortest paths. ACM Transactions on Algorithms, 1(2):283-323, 2005. URL: https://doi.org/10.1145/1103963.1103968.
  18. Michael Elkin, Arnold Filtser, and Ofer Neiman. Distributed construction of light networks. In Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 483-492, 2020. Google Scholar
  19. Michael Elkin and David Peleg. (1+ε,β)-spanner constructions for general graphs. SIAM Journal on Computing, 33(3):608-631, 2004. URL: https://doi.org/10.1137/S0097539701393384.
  20. Michael Elkin and Jian Zhang. Efficient algorithms for constructing (1+ε,β)-spanners in the distributed and streaming models. Distributed Computing, 18(5):375-385, 2006. URL: https://doi.org/10.1007/s00446-005-0147-2.
  21. David Eppstein. Spanning trees and spanners. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 425-461. North-Holland, 2000. URL: https://doi.org/10.1016/B978-044482537-7/50010-3.
  22. David Eppstein and Siddharth Gupta. Crossing patterns in nonplanar road networks. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 1-9, 2017. Google Scholar
  23. David Eppstein and Hadi Khodabandeh. On the edge crossings of the greedy spanner. In 37th International Symposium on Computational Geometry, volume 12, page 37, 2021. Google Scholar
  24. David Eppstein and Hadi Khodabandeh. Optimal spanners for unit ball graphs in doubling metrics. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.15234.
  25. Mohammad Farshi and Joachim Gudmundsson. Experimental study of geometric t-spanners. ACM Journal of Experimental Algorithmics, 14:1.3:1-1.3:29, 2009. URL: https://doi.org/10.1145/1498698.1564499.
  26. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the streaming model: the value of space. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 745-754. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  27. Arnold Filtser and Shay Solomon. The greedy spanner is existentially optimal. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 9-17, 2016. Google Scholar
  28. Jie Gao, Leonidas J Guibas, John Hershberger, Li Zhang, and An Zhu. Geometric spanners for routing in mobile networks. IEEE journal on selected areas in communications, 23(1):174-185, 2005. Google Scholar
  29. Lee-Ad Gottlieb. A light metric spanner. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 759-772. IEEE, 2015. URL: https://doi.org/10.1109/FOCS.2015.52.
  30. Joachim Gudmundsson, Christos Levcopoulos, and Giri Narasimhan. Fast greedy algorithms for constructing sparse geometric spanners. SIAM Journal on Computing, 31(5):1479-1500, 2002. Google Scholar
  31. Jonathan P Jenkins, Iyad A Kanj, Ge Xia, and Fenghui Zhang. Local construction of spanners in the 3d space. IEEE Transactions on Mobile Computing, 11(7):1140-1150, 2012. Google Scholar
  32. Lujun Jia, Rajmohan Rajaraman, and Christian Scheideler. On local algorithms for topology control and routing in ad hoc networks. In Proceedings of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 220-229. ACM, 2003. URL: https://doi.org/10.1145/777412.777447.
  33. Iyad A Kanj, Ljubomir Perković, and Ge Xia. Computing lightweight spanners locally. In International Symposium on Distributed Computing, pages 365-378. Springer, 2008. Google Scholar
  34. J. Mark Keil. Approximating the complete Euclidean graph. In Rolf Karlsson and Andrzej Lingas, editors, Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT), volume 318 of Lecture Notes in Computer Science, pages 208-213. Springer, 1988. URL: https://doi.org/10.1007/3-540-19487-8_23.
  35. Fabian Kuhn, Thomas Moscibroda, and Rogert Wattenhofer. On the locality of bounded growth. In Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pages 60-68, 2005. Google Scholar
  36. Hung Le and Shay Solomon. Truly optimal Euclidean spanners. In Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1078-1100. IEEE, 2019. URL: https://doi.org/10.1109/FOCS.2019.00069.
  37. Ning Li, Jennifer C Hou, and Lui Sha. Design and analysis of an mst-based topology control algorithm. IEEE Transactions on Wireless Communications, 4(3):1195-1206, 2005. Google Scholar
  38. Xiang-Yang Li, Gruia Calinescu, Peng-Jun Wan, and Yu Wang. Localized delaunay triangulation with application in ad hoc wireless networks. IEEE Transactions on Parallel and Distributed Systems, 14(10):1035-1047, 2003. Google Scholar
  39. Xiang-Yang Li, Peng-Jun Wan, and Yu Wang. Power efficient and sparse spanner for wireless ad hoc networks. In Proceedings Tenth International Conference on Computer Communications and Networks (Cat. No. 01EX495), pages 564-567. IEEE, 2001. Google Scholar
  40. James D. Marble and Kostas E. Bekris. Asymptotically near-optimal planning with probabilistic roadmap spanners. IEEE Transactions on Robotics, 29(2):432-444, 2013. URL: https://doi.org/10.1109/TRO.2012.2234312.
  41. Giri Narasimhan and Michiel Smid. Geometric spanner networks. Cambridge University Press, 2007. Google Scholar
  42. David Peleg and Liam Roditty. Localized spanner construction for ad hoc networks with variable transmission range. ACM Transactions on Sensor Networks (TOSN), 7(3):1-14, 2010. Google Scholar
  43. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: https://doi.org/10.1002/jgt.3190130114.
  44. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389-401, 2011. URL: https://doi.org/10.1007/s00453-010-9401-5.
  45. Johannes Schneider and Roger Wattenhofer. 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, pages 35-44, 2008. Google Scholar
  46. Michiel Smid. The weak gap property in metric spaces of bounded doubling dimension. In Efficient Algorithms, pages 275-289. Springer, 2009. Google Scholar
  47. Wenjie Wang, Cheng Jin, and Sugih Jamin. Network overlay construction under limited end-to-end reachability. In Proceedings of the 24th Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), volume 3, pages 2124-2134. IEEE, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact