The Sparsest Additive Spanner via Multiple Weighted BFS Trees
From MaRDI portal
Publication:5091078
DOI10.4230/LIPIcs.OPODIS.2018.7MaRDI QIDQ5091078
Ami Paz, Keren Censor-Hillel, Noam Ravid
Publication date: 21 July 2022
Full work available at URL: https://dblp.uni-trier.de/db/journals/corr/corr1811.html#abs-1811-01997
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
68M14: Distributed systems
Cites Work
- Fast deterministic distributed algorithms for sparse spanners
- Near-linear lower bounds for distributed distance computations, even in sparse networks
- Vertex fault tolerant additive spanners
- The sparsest additive spanner via multiple weighted BFS trees
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Distributed distance computation and routing with small messages
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
- Optimal distributed all pairs shortest paths and applications
- On the locality of distributed sparse spanner construction
- New Pairwise Spanners
- Improved Distributed Approximate Matching
- Additive Spanners: A Simple Construction
- Additive spanners and (α, β)-spanners
- Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
- Additive Spanners in Nearly Quadratic Time
- Local Computation of Nearly Additive Spanners
- Graph spanners
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Distributed Computing: A Locality-Sensitive Approach
- Error Amplification for Pairwise Spanner Lower Bounds
- The 4/3 Additive Spanner Exponent Is Tight
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Distributed Verification and Hardness of Distributed Approximation
- Distributed exact shortest paths in sublinear time
- Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
- Congested Clique Algorithms for Graph Spanners
- Compact routing schemes with improved stretch
- Efficient distributed source detection with limited bandwidth
- Distributed Spanner Approximation
- A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds
- Improved distributed algorithms for exact shortest paths
- Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
- Distributed approximation algorithms for weighted shortest paths
- 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
- Global computation in a poorly connected world
- Computing almost shortest paths
- Distributed construction of purely additive spanners
- Distributed algorithms for ultrasparse spanners and linear size skeletons
