Error Amplification for Pairwise Spanner Lower Bounds

DOI10.1137/1.9781611974331.CH60MaRDI QIDQ4575639zbMATH OpenOpenAlexFDO

Authors Amir Abboud, Greg Bodwin

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

Mathematics Subject Classification ID

Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On additive spanners in weighted graphs with local error
• Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree
• Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree
• On Pairwise Spanners
• Lower bound for sparse Euclidean spanners
• A hierarchy of lower bounds for sublinear additive spanners
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel
• From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
• scientific article; zbMATH DE number 7238981

Cited in

(10)

• New pairwise spanners
• Graph spanners: a tutorial review
• A note on distance-preserving graph sparsification
• The sparsest additive spanner via multiple weighted BFS trees
• A hierarchy of lower bounds for sublinear additive spanners
• Near-optimal distance emulator for planar graphs
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• New results on linear size distance preservers
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Multi-priority graph sparsification

This page was built for publication: Error Amplification for Pairwise Spanner Lower Bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575639)