Error Amplification for Pairwise Spanner Lower Bounds
From MaRDI portal
Publication:4575639
DOI10.1137/1.9781611974331.ch60zbMath1410.68264OpenAlexW4235516325MaRDI QIDQ4575639
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://doi.org/10.1137/1.9781611974331.ch60
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (11)
A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ New pairwise spanners ⋮ Multi-priority graph sparsification ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Unnamed Item ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ A note on distance-preserving graph sparsification ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ New Results on Linear Size Distance Preservers
This page was built for publication: Error Amplification for Pairwise Spanner Lower Bounds
