The sparsest additive spanner via multiple weighted BFS trees
From MaRDI portal
Publication:2201997
DOI10.1016/J.TCS.2020.05.035zbMATH Open1461.68146arXiv1811.01997OpenAlexW2952039123MaRDI QIDQ2201997FDOQ2201997
Authors: Keren Censor-Hillel, Ami Paz, Noam Ravid 
Publication date: 17 September 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
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, a 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 roughly O(n^{4/3}) edges. We then show a distributed implementation of our algorithm, answering an open problem in [Censor-Hillel et al., DISC 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.
Full work available at URL: https://arxiv.org/abs/1811.01997
Recommendations
Cites Work
- Optimal distributed all pairs shortest paths and applications
- Distributed Computing: A Locality-Sensitive Approach
- Distributed verification and hardness of distributed approximation
- Distributed approximation algorithms for weighted shortest paths
- Computing almost shortest paths
- An Optimal Synchronizer for the Hypercube
- Graph spanners
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Global computation in a poorly connected world
- Additive spanners and \(({\alpha}, {\beta})\)-spanners
- Matching is as easy as matrix inversion
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
- Improved Distributed Approximate Matching
- A trade-off between space and efficiency for routing tables
- Compact routing schemes with improved stretch
- Distributed Spanner Approximation
- Improved deterministic distributed construction of spanners
- Fast deterministic distributed algorithms for sparse spanners
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- The 4/3 additive spanner exponent is tight
- Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
- Efficient algorithms for constructing very sparse spanners and emulators
- Improved distributed algorithms for exact shortest paths
- Near-linear lower bounds for distributed distance computations, even in sparse networks
- Distributed distance computation and routing with small messages
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- On the locality of distributed sparse spanner construction
- Additive spanners: a simple construction
- New pairwise spanners
- Additive spanners in nearly quadratic time
- Error Amplification for Pairwise Spanner Lower Bounds
- Efficient distributed source detection with limited bandwidth
- Hopsets with constant hopbound, and applications to approximate shortest paths
- Congested clique algorithms for graph spanners
- A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds
- Distributed exact weighted all-pairs shortest paths in near-linear time
- Derandomizing distributed algorithms with small messages: spanners and dominating set
- Local Computation of Nearly Additive Spanners
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
Cited In (6)
This page was built for publication: The sparsest additive spanner via multiple weighted BFS trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201997)
