Thorup-Zwick emulators are universally optimal hopsets

DOI10.1016/j.ipl.2018.10.001zbMath1470.68059arXiv1705.00327OpenAlexW2963983736MaRDI QIDQ1628677

Seth Pettie, Shang-En Huang

Publication date: 5 December 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.00327

zbMATH Keywords

graph algorithmsemulatorsapproximate shortest pathshopsets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (7)

Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Graph spanners: a tutorial review ⋮ Fast approximate shortest paths in the congested clique ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ New Results on Linear Size Distance Preservers

Cites Work

• Unnamed Item
• Unnamed Item
• On sparse spanners of weighted graphs
• Using Selective Path-Doubling for Parallel Shortest-Path Computations
• Additive Spanners: A Simple Construction
• Additive spanners and (α, β)-spanners
• High-Probability Parallel Transitive-Closure Algorithms
• Approximate distance oracles
• Spanners and emulators with sublinear distance errors
• Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• A Randomized Parallel Algorithm for Single-Source Shortest Paths
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• All-Pairs Almost Shortest Paths
• Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

This page was built for publication: Thorup-Zwick emulators are universally optimal hopsets