Small Stretch Pairwise Spanners and Approximate $D$-Preservers
From MaRDI portal
Publication:3452163
DOI10.1137/140953927zbMath1327.05090MaRDI 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
68W40: Analysis of algorithms
05C12: Distance in graphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
A Hierarchy of Lower Bounds for Sublinear Additive Spanners, Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal, New Results on Linear Size Distance Preservers, New pairwise spanners, A note on distance-preserving graph sparsification, On additive spanners in weighted graphs with local error
Cites Work
- Unnamed Item
- Unnamed Item
- On the ratio of optimal integral and fractional covers
- Compact Routing with Minimum Stretch
- Low distortion spanners
- 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
