Sparse Distance Preservers and Additive Spanners

DOI10.1137/S0895480103431046zbMath1103.05027OpenAlexW2082352769MaRDI QIDQ5470808

Béla Bollobás, Don Coppersmith, Michael Elkin

Publication date: 1 June 2006

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480103431046

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Small Stretch Pairwise Spanners and Approximate $D$-Preservers, A Hierarchy of Lower Bounds for Sublinear Additive Spanners, A story of diameter, radius, and (almost) Helly property, Improved weighted additive spanners, Reachability Preservers: New Extremal Bounds and Approximation Algorithms, Relaxed spanners for directed disk graphs, New pairwise spanners, Unnamed Item, Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners, Distributed construction of purely additive spanners, Graph spanners: a tutorial review, Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones, New Results on Linear Size Distance Preservers