New pairwise spanners
From MaRDI portal
Publication:1693988
DOI10.1007/s00224-016-9736-7zbMath1386.05185OpenAlexW2562627112MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
On additive spanners in weighted graphs with local error ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Multi-priority graph sparsification ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Graph spanners: a tutorial review ⋮ A note on distance-preserving graph sparsification ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ New Results on Linear Size Distance Preservers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On sparse spanners of weighted graphs
- 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
- 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
This page was built for publication: New pairwise spanners
