Sparse Sourcewise and Pairwise Distance Preservers

DOI10.1137/050630696MaRDI QIDQ3440267zbMATH OpenOpenAlexFDO

Authors Don Coppersmith, Michael Elkin

Publication date 22 May 2007

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

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

zbMATH Keywords

distance preservationspanners

Mathematics Subject Classification ID

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

Recommendations

• Sparse source-wise and pair-wise distance preservers
• Sparse Distance Preservers and Additive Spanners
• scientific article; zbMATH DE number 2079365
• Sparse distance metric learning
• Improving proximity bounds using sparsity
• The kernel semi-least squares method for sparse distance approximation
• Metric sparsification and operator norm localization
• A note on distance-preserving graph sparsification

Cited in

(40)

• Graph spanners: a tutorial review
• A fast algorithm for source-wise round-trip spanners
• A note on distance-preserving graph sparsification
• Light spanners for high dimensional norms via stochastic decompositions
• Demand-aware network designs of bounded degree
• Source-wise round-trip spanners
• Assisted identification of mode of operation in binary code with dynamic data flow slicing
• Sparse source-wise and pair-wise distance preservers
• Improved purely additive fault-tolerant spanners
• A hierarchy of lower bounds for sublinear additive spanners
• Linear size distance preservers
• Reachability preservers: new extremal bounds and approximation algorithms
• Near-optimal distance emulator for planar graphs
• Light spanners for high dimensional norms via stochastic decompositions
• Lossless prioritized embeddings
• Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
• Distance-preserving subgraphs of interval graphs
• Improved guarantees for vertex sparsification in planar graphs
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
• Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
• Improved guarantees for vertex sparsification in planar graphs
• Distance-Preserving Graph Contractions
• New results on linear size distance preservers
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Almost-optimal sublinear additive spanners
• Improved sourcewise roundtrip spanners with constant stretch
• Scattering and sparse partitions, and their applications
• New extremal bounds for reachability and strong-connectivity preservers under failures
• New fault tolerant subset preservers
• Simple approximations for general spanner problems
• Path-reporting distance oracles with logarithmic stretch and linear size
• Additive spanner lower bounds with optimal inner graph structure
• The discrepancy of shortest paths
• Are there graphs whose shortest path structure requires large edge weights?
• New extremal bounds for reachability and strong-connectivity preservers under failures
• Scattering and sparse partitions, and their applications
• Graph spanners for group Steiner distances
• Controllability backbone in multiagent networks
• Isometric-universal graphs for trees

This page was built for publication: Sparse Sourcewise and Pairwise Distance Preservers

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