License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.7
URN: urn:nbn:de:0030-drops-100676
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10067/
Censor-Hillel, Keren ;
Paz, Ami ;
Ravid, Noam
The Sparsest Additive Spanner via Multiple Weighted BFS Trees
Abstract
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.
BibTeX - Entry
@InProceedings{censorhillel_et_al:LIPIcs:2018:10067,
author = {Keren Censor-Hillel and Ami Paz and Noam Ravid},
title = {{The Sparsest Additive Spanner via Multiple Weighted BFS Trees}},
booktitle = {22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
pages = {7:1--7:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-098-9},
ISSN = {1868-8969},
year = {2018},
volume = {125},
editor = {Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10067},
URN = {urn:nbn:de:0030-drops-100676},
doi = {10.4230/LIPIcs.OPODIS.2018.7},
annote = {Keywords: Distributed graph algorithms, congest model, weighted BFS trees, additive spanners}
}
|
Keywords: |
|
Distributed graph algorithms, congest model, weighted BFS trees, additive spanners |
|
Collection: |
|
22nd International Conference on Principles of Distributed Systems (OPODIS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
15.01.2019 |
