2026-07-23T00:26:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10067 2024-03-06T10:45:32Z ddc:004 open_access

The Sparsest Additive Spanner via Multiple Weighted BFS Trees Censor-Hillel, Keren Paz, Ami Ravid, Noam Distributed graph algorithms congest model weighted BFS trees additive spanners Spanners are fundamental graph structures that sparsify graphs at the cost of small stretch. In particular, in recent years, many sequential algorithms constructing additive all-pairs spanners were designed, providing very sparse small-stretch subgraphs. Remarkably, it was then shown that the known (+6)-spanner constructions are essentially the sparsest possible, that is, larger additive stretch cannot guarantee a sparser spanner, which brought the stretch-sparsity trade-off to its limit. Distributed constructions of spanners are also abundant. However, for additive spanners, while there were algorithms constructing (+2) and (+4)-all-pairs spanners, the sparsest case of (+6)-spanners remained elusive. We remedy this by designing a new sequential algorithm for constructing a (+6)-spanner with the essentially-optimal sparsity of O~(n^{4/3}) edges. We then show a distributed implementation of our algorithm, answering an open problem in [Keren Censor{-}Hillel et al., 2016]. A main ingredient in our distributed algorithm is an efficient construction of multiple weighted BFS trees. A weighted BFS tree is a BFS tree in a weighted graph, that consists of the lightest among all shortest paths from the root to each node. We present a distributed algorithm in the CONGEST model, that constructs multiple weighted BFS trees in |S|+D-1 rounds, where S is the set of sources and D is the diameter of the network graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Keren Censor-Hillel and Ami Paz and Noam Ravid 2019 Is Part Of LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2018.7 urn:nbn:de:0030-drops-100676 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.7 eng https://creativecommons.org/licenses/by/3.0/legalcode