Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Censor-Hillel, Keren; Paz, Ami; Ravid, Noam http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-100676
URL:

; ;

The Sparsest Additive Spanner via Multiple Weighted BFS Trees

pdf-format:


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
Seminar: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue date: 2018
Date of publication: 2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI