New pairwise spanners
From MaRDI portal
Publication:1693988
DOI10.1007/s00224-016-9736-7zbMath1386.05185MaRDI QIDQ1693988
Publication date: 1 February 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-016-9736-7
68Q25: Analysis of algorithms and problem complexity
05C38: Paths and cycles
05C12: Distance in graphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems, New Results on Linear Size Distance Preservers, Graph spanners: a tutorial review, A note on distance-preserving graph sparsification, The sparsest additive spanner via multiple weighted BFS trees, On additive spanners in weighted graphs with local error
Cites Work
- Unnamed Item
- Unnamed Item
- On sparse spanners of weighted graphs
- 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
- Small Stretch Pairwise Spanners and Approximate $D$-Preservers
- 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)
- Error Amplification for Pairwise Spanner Lower Bounds
- Better Distance Preservers and Additive Spanners
- $(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
- The 4/3 additive spanner exponent is tight
- 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
