Spanners and emulators with sublinear distance errors

DOI10.1145/1109557.1109645zbMath1192.05041OpenAlexW4239180782WikidataQ60299152 ScholiaQ60299152MaRDI QIDQ3581551

Mikkel Thorup, Uri Zwick

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109645

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Related Items (33)

Thorup-Zwick emulators are universally optimal hopsets ⋮ Source-wise round-trip spanners ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Covering metric spaces by few trees ⋮ Deterministic improved round-trip spanners ⋮ Demand-aware network designs of bounded degree ⋮ Improved weighted additive spanners ⋮ New pairwise spanners ⋮ Unnamed Item ⋮ Sublinear fully distributed partition with applications ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Preprocess, set, query! ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ Approximating Shortest Paths in Graphs ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Close to linear space routing schemes ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Multiplicative Approximations of Random Walk Transition Probabilities ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ Covering Metric Spaces by Few Trees ⋮ On Approximate Distance Labels and Routing Schemes with Affine Stretch ⋮ Fast approximate shortest paths in the congested clique ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners

This page was built for publication: Spanners and emulators with sublinear distance errors