Better Distance Preservers and Additive Spanners

DOI10.1137/1.9781611974331.ch61zbMath1410.05034arXiv1505.05599OpenAlexW2953285790MaRDI QIDQ4575640

Greg Bodwin, Virginia Vassilevska Williams

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Distance in graphs (05C12)

Related Items (13)

A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Improved weighted additive spanners ⋮ New pairwise spanners ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ Unnamed Item ⋮ Light Euclidean Spanners with Steiner Points ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ Unnamed Item ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Distance-Preserving Graph Contractions ⋮ New Results on Linear Size Distance Preservers

This page was built for publication: Better Distance Preservers and Additive Spanners