Small Stretch Pairwise Spanners and Approximate $D$-Preservers
From MaRDI portal
Publication:3452163
DOI10.1137/140953927zbMath1327.05090OpenAlexW2196216888MaRDI QIDQ3452163
Telikepalli Kavitha, Nithin Varma
Publication date: 18 November 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/140953927
Analysis of algorithms (68W40) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (7)
A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ On additive spanners in weighted graphs with local error ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ New pairwise spanners ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ A note on distance-preserving graph sparsification ⋮ New Results on Linear Size Distance Preservers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the ratio of optimal integral and fractional covers
- Compact Routing with Minimum Stretch
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- New Pairwise Spanners
- On Pairwise Spanners
- Additive Spanners: A Simple Construction
- Additive spanners and (α, β)-spanners
- Über ein Problem von K. Zarankiewicz
- Approximate distance oracles
- Spanners and emulators with sublinear distance errors
- Additive Spanners in Nearly Quadratic Time
- Graph spanners
- A Greedy Heuristic for the Set-Covering Problem
- Routing with Polynomial Communication-Space Trade-Off
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- An Optimal Synchronizer for the Hypercube
- Compact roundtrip routing in directed networks
- All-Pairs Almost Shortest Paths
- Proximity-preserving labeling schemes
- Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Small Stretch Pairwise Spanners
- Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs
- Algorithms – ESA 2004
- Sparse Distance Preservers and Additive Spanners
- Automata, Languages and Programming
- New Additive Spanners
- Computing almost shortest paths
This page was built for publication: Small Stretch Pairwise Spanners and Approximate $D$-Preservers
