Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
From MaRDI portal
Publication:5233107
DOI10.1137/18M1166791zbMath1430.68197arXiv1605.04538OpenAlexW2970898478WikidataQ127314607 ScholiaQ127314607MaRDI QIDQ5233107
Publication date: 16 September 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1605.04538
Related Items (10)
Single-source shortest paths in the CONGEST model with improved bounds ⋮ Improved weighted additive spanners ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Graph spanners: a tutorial review ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Fast approximate shortest paths in the congested clique ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
Cites Work
- Unnamed Item
- Unnamed Item
- Thorup-Zwick emulators are universally optimal hopsets
- Algebraic methods in the congested clique
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Fast Partial Distance Estimation and Applications
- Using Selective Path-Doubling for Parallel Shortest-Path Computations
- High-Probability Parallel Transitive-Closure Algorithms
- Spanners and emulators with sublinear distance errors
- Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
- 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
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
- (1 + εΒ) -spanner constructions for general graphs
- Approximate distance oracles
- Distributed approximation algorithms for weighted shortest paths
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- On Efficient Distributed Construction of Near Optimal Routing Schemes
- Computing almost shortest paths
- Small hop-diameter sparse spanners for doubling metrics
This page was built for publication: Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
