A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

Related Items (1)

Distributed Symmetry Breaking on Power Graphs via Sparsification

Uses Software

Graphs

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Superlinear lower bounds for multipass graph processing
Tight bounds for distributed minimum-weight spanning tree verification
On dynamic shortest paths problems
Efficient distributed computation of distance sketches in networks
Streaming algorithm for graph spanners-single pass and constant processing time per edge
Structure preserving reductions among convex optimization problems
Approximation algorithms for combinatorial problems
Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
On efficient distributed construction of near optimal routing schemes
A fast distributed approximation algorithm for minimum spanning trees
Algebraic methods in the congested clique
Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
Fully dynamic all pairs shortest paths with real edge weights
On graph problems in a semi-streaming model
A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
Near-Optimal Distributed Maximum Flow
Fast Partial Distance Estimation and Applications
Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
Distributed Minimum Cut Approximation
Optimal distributed all pairs shortest paths and applications
Can quantum communication speed up distributed computation?
Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
Fast computation of small cuts via cycle space sampling
High-Probability Parallel Transitive-Closure Algorithms
On a routing problem
An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
All pairs shortest paths using bridging sets and rectangular matrix multiplication
Approximate distance oracles
Distributed Approximate Matching
Spanners and emulators with sublinear distance errors
Graph Distances in the Data-Stream Model
Parallel Symmetry-Breaking in Sparse Graphs
Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
Fast Distributed Construction of Smallk-Dominating Sets and Applications
A Randomized Parallel Algorithm for Single-Source Shortest Paths
A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
Polylog-time and near-linear work approximation scheme for undirected shortest paths
Distributed Computing: A Locality-Sensitive Approach
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Parallel Metric Tree Embedding Based on an Algebraic View on Moore-Bellman-Ford
Distributed Verification and Hardness of Distributed Approximation
“Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
Distributed exact shortest paths in sublinear time
Distributed Graph Coloring: Fundamentals and Recent Developments
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
Optimal deterministic routing and sorting on the congested clique
Efficient distributed source detection with limited bandwidth
Shortest-path queries in static networks
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
Distributed approximation algorithms for weighted shortest paths
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
Fast routing table construction using small messages
Almost-Tight Distributed Minimum Cut Algorithms
Automata, Languages and Programming
Computing and Combinatorics
Trading off space for passes in graph streaming problems
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
Efficient distributed approximation algorithms via probabilistic tree embeddings

This page was built for publication: A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths