2026-10-19T15:20:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11311 2024-03-06T09:47:55Z ddc:004 open_access

Distributed Algorithms for Low Stretch Spanning Trees Becker, Ruben Emek, Yuval Ghaffari, Mohsen Lenzen, Christoph distributed graph algorithms low-stretch spanning trees CONGEST model ball decomposition star decomposition 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ruben Becker and Yuval Emek and Mohsen Ghaffari and Christoph Lenzen 2019 Is Part Of LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2019.4 urn:nbn:de:0030-drops-113116 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.4 eng https://creativecommons.org/licenses/by/3.0/legalcode