New pairwise spanners
From MaRDI portal
Recommendations
Cites work
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- A Greedy Heuristic for the Set-Covering Problem
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Additive spanners and \(({\alpha}, {\beta})\)-spanners
- Additive spanners in nearly quadratic time
- Additive spanners: a simple construction
- Algorithms – ESA 2004
- All-Pairs Almost Shortest Paths
- An Optimal Synchronizer for the Hypercube
- Approximate distance oracles
- Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
- Automata, Languages and Programming
- Better distance preservers and additive spanners
- Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
- Compact roundtrip routing in directed networks
- Compact routing with minimum stretch
- Computing almost shortest paths
- Distance labeling in graphs (extended abstract)
- Error Amplification for Pairwise Spanner Lower Bounds
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Faster algorithms for all-pairs approximate shortest paths in undirected graphs
- Graph spanners
- Low distortion spanners
- Near-Linear Time Construction of Sparse Neighborhood Covers
- New additive spanners
- New pairwise spanners
- On Pairwise Spanners
- On sparse spanners of weighted graphs
- On the ratio of optimal integral and fractional covers
- Proximity-preserving labeling schemes
- Routing with Polynomial Communication-Space Trade-Off
- Small stretch pairwise spanners and approximate \(D\)-preservers
- Spanners and emulators with sublinear distance errors
- Sparse Distance Preservers and Additive Spanners
- Sparse source-wise and pair-wise distance preservers
- The 4/3 additive spanner exponent is tight
Cited in
(15)- New (α, β) Spanners and Hopsets
- Graph spanners: a tutorial review
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- The sparsest additive spanner via multiple weighted BFS trees
- New results on linear size distance preservers
- Multi-priority graph sparsification
- A note on distance-preserving graph sparsification
- New additive spanners
- On additive spanners in weighted graphs with local error
- On Pairwise Spanners
- New pairwise spanners
- Almost-optimal sublinear additive spanners
- Small stretch pairwise spanners and approximate \(D\)-preservers
- Graphs with small additive stretch number
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
This page was built for publication: New pairwise spanners
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1693988)
