Distributed construction of purely additive spanners

DOI10.1007/s00446-017-0306-2zbMath1451.68345arXiv1607.05597OpenAlexW2494849242MaRDI 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Communication complexity, information complexity (68Q11)

Related Items (9)

On additive spanners in weighted graphs with local error ⋮ Communication-efficient distributed graph clustering and sparsification under duplication models ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ Message lower bounds via efficient network synchronization ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Distributed Spanner Approximation

Cites Work

• Unnamed Item
• 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
• 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

This page was built for publication: Distributed construction of purely additive spanners