Sparse Sourcewise and Pairwise Distance Preservers
From MaRDI portal
Publication:3440267
DOI10.1137/050630696zbMath1118.05025OpenAlexW2031536548MaRDI QIDQ3440267
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
Combinatorics in computer science (68R05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (24)
On resilient graph spanners ⋮ Source-wise round-trip spanners ⋮ Improved Purely Additive Fault-Tolerant Spanners ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Lossless Prioritized Embeddings ⋮ Demand-aware network designs of bounded degree ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Assisted Identification of Mode of Operation in Binary Code with Dynamic Data Flow Slicing ⋮ A note on distance-preserving graph sparsification ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ Distance-Preserving Graph Contractions ⋮ Distance-Preserving Subgraphs of Interval Graphs ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ New Results on Linear Size Distance Preservers
This page was built for publication: Sparse Sourcewise and Pairwise Distance Preservers
