Sparse Distance Preservers and Additive Spanners

DOI10.1137/S0895480103431046MaRDI QIDQ5470808zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 2079365
• Small stretch pairwise spanners and approximate D-preservers
• Sublinear Distance Labeling
• Better distance preservers and additive spanners
• Sparse source-wise and pair-wise distance preservers

Cited in

(20)

• Graph spanners: a tutorial review
• Steiner shallow-light trees are exponentially lighter than spanning ones
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• A story of diameter, radius, and (almost) Helly property
• scientific article; zbMATH DE number 2079365 (Why is no real title available?)
• Additive sparsification of CSPs
• A hierarchy of lower bounds for sublinear additive spanners
• Distance-preserving subgraphs of interval graphs
• Near-optimal distance emulator for planar graphs
• New results on linear size distance preservers
• New fault tolerant subset preservers
• Improved weighted additive spanners
• Relaxed spanners for directed disk graphs
• Additive spanner lower bounds with optimal inner graph structure
• New pairwise spanners
• Small stretch pairwise spanners and approximate D-preservers
• Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
• Better distance preservers and additive spanners
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Sparse Sourcewise and Pairwise Distance Preservers

This page was built for publication: Sparse Distance Preservers and Additive Spanners

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