Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.4
URN: urn:nbn:de:0030-drops-113116
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11311/
Becker, Ruben ; Emek, Yuval ; Ghaffari, Mohsen ; Lenzen, Christoph
Distributed Algorithms for Low Stretch Spanning Trees
| pdf-format: |
|
Abstract
Given an undirected graph with integer edge lengths, we study the problem of approximating the distances in the graph by a spanning tree based on the notion of stretch. Our main contribution is a distributed algorithm in the CONGEST model of computation that constructs a random spanning tree with the guarantee that the expected stretch of every edge is O(log^{3} n), where n is the number of nodes in the graph. If the graph is unweighted, then this algorithm can be implemented to run in O(D) rounds, where D is the hop-diameter of the graph, thus being asymptotically optimal. In the weighted case, the run-time of our algorithm matches the currently best known bound for exact distance computations, i.e., O~ (min{sqrt{n D}, sqrt{n} D^{1 / 4} + n^{3 / 5} + D}). We stress that this is the first distributed construction of spanning trees leading to poly-logarithmic expected stretch with non-trivial running time.
BibTeX - Entry
@InProceedings{becker_et_al:LIPIcs:2019:11311,
author = {Ruben Becker and Yuval Emek and Mohsen Ghaffari and Christoph Lenzen},
title = {{Distributed Algorithms for Low Stretch Spanning Trees}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {4:1--4:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-126-9},
ISSN = {1868-8969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11311},
URN = {urn:nbn:de:0030-drops-113116},
doi = {10.4230/LIPIcs.DISC.2019.4},
annote = {Keywords: distributed graph algorithms, low-stretch spanning trees, CONGEST model, ball decomposition, star decomposition}
}
| Keywords: | distributed graph algorithms, low-stretch spanning trees, CONGEST model, ball decomposition, star decomposition | |
| Seminar: | 33rd International Symposium on Distributed Computing (DISC 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 08.10.2019 |
