Distributed construction of purely additive spanners
From MaRDI portal
Publication:5915631
DOI10.1007/s00446-017-0306-2zbMath1451.68345arXiv1607.05597MaRDI QIDQ5915631
Keren Censor-Hillel, Ami Paz, Amir Yehudayoff, Telikepalli Kavitha
Publication date: 1 June 2018
Published in: Lecture Notes in Computer Science, Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.05597
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
68R10: Graph theory (including graph drawing) in computer science
68W15: Distributed algorithms
68Q11: Communication complexity, information complexity
Related Items
Distributed Spanner Approximation, The Sparsest Additive Spanner via Multiple Weighted BFS Trees, Distributed construction of purely additive spanners, Communication-efficient distributed graph clustering and sparsification under duplication models, Graph spanners: a tutorial review, The sparsest additive spanner via multiple weighted BFS trees, Fooling views: a new lower bound technique for distributed computations under congestion, Message lower bounds via efficient network synchronization, On additive spanners in weighted graphs with local error
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On dynamic shortest paths problems
- Fast deterministic distributed algorithms for sparse spanners
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- On sparse spanners of weighted graphs
- 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
- Distributed Minimum Cut Approximation
- Low distortion spanners
- Optimal distributed all pairs shortest paths and applications
- On the locality of distributed sparse spanner construction
- Distributed connectivity decomposition
- On the power of the congested clique model
- New Pairwise Spanners
- On Pairwise Spanners
- Distributed Algorithms for Network Diameter and Girth
- Additive Spanners: A Simple Construction
- Additive spanners and (α, β)-spanners
- Fully dynamic randomized algorithms for graph spanners
- Sparse Sourcewise and Pairwise Distance Preservers
- Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
- Approximate distance oracles
- Spanners and emulators with sublinear distance errors
- Additive Spanners in Nearly Quadratic Time
- Local Computation of Nearly Additive Spanners
- Graph spanners
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Distributed Computing: A Locality-Sensitive Approach
- Error Amplification for Pairwise Spanner Lower Bounds
- Better Distance Preservers and Additive Spanners
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Communication Complexity
- Distributed Verification and Hardness of Distributed Approximation
- All-Pairs Almost Shortest Paths
- Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
- Compact routing schemes with improved stretch
- Efficient distributed source detection with limited bandwidth
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Small Stretch Pairwise Spanners
- The 4/3 additive spanner exponent is tight
- A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
- Global computation in a poorly connected world
- Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
- Probability and Computing
- Sparse Distance Preservers and Additive Spanners
- Automata, Languages and Programming
- New Additive Spanners
- Computing almost shortest paths
- Distributed construction of purely additive spanners
- Distributed algorithms for ultrasparse spanners and linear size skeletons
