Additive Spanners: A Simple Construction
From MaRDI portal
Publication:3188902
DOI10.1007/978-3-319-08404-6_24zbMath1417.05219arXiv1403.0178OpenAlexW1937137463MaRDI QIDQ3188902
Publication date: 2 September 2014
Published in: Algorithm Theory – SWAT 2014 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1403.0178
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Thorup-Zwick emulators are universally optimal hopsets ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ On additive spanners in weighted graphs with local error ⋮ Vertex fault tolerant additive spanners ⋮ Improved weighted additive spanners ⋮ New pairwise spanners ⋮ Multi-priority graph sparsification ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ Unnamed Item ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ A note on distance-preserving graph sparsification ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees
