Very Sparse Additive Spanners and Emulators

DOI10.1145/2688073.2688103zbMath1365.05275arXiv1505.05630OpenAlexW2093429583MaRDI QIDQ2989053

Gregory Bodwin, Virginia Vassilevska Williams

Publication date: 19 May 2017

Published in: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph spannersgraph algorithmsgraph emulators

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Improved weighted additive spanners ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Unnamed Item ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ New Results on Linear Size Distance Preservers

This page was built for publication: Very Sparse Additive Spanners and Emulators