License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.21
URN: urn:nbn:de:0030-drops-172129
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17212/
Eppstein, David ;
Khodabandeh, Hadi
Distributed Construction of Lightweight Spanners for Unit Ball Graphs
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.
BibTeX - Entry
@InProceedings{eppstein_et_al:LIPIcs.DISC.2022.21,
author = {Eppstein, David and Khodabandeh, Hadi},
title = {{Distributed Construction of Lightweight Spanners for Unit Ball Graphs}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {21:1--21:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-255-6},
ISSN = {1868-8969},
year = {2022},
volume = {246},
editor = {Scheideler, Christian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17212},
URN = {urn:nbn:de:0030-drops-172129},
doi = {10.4230/LIPIcs.DISC.2022.21},
annote = {Keywords: spanners, doubling metrics, distributed, topology control}
}
|
Keywords: |
|
spanners, doubling metrics, distributed, topology control |
|
Collection: |
|
36th International Symposium on Distributed Computing (DISC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
17.10.2022 |
