New pairwise spanners
Let \(G=(V,E)\) be an undirected unweighted graph on \(n\) vertices. A subgraph \(H\) of \(G\) is called an (all-pairs) purely additive spanner with stretch \(\beta\) if for every \((u,v)\in V\times V\), \(\operatorname{dist}_H(u,v)\leq \operatorname{dist}_G(u,v)+\beta\). The following problem is considered in this paper. Given \(\mathcal{P}\subseteq V\times V\) then seek a sparse subgraph \(H\) where \(\operatorname{dist}_H(u,v)\leq \operatorname{dist}_G(u,v)+\beta\) for each \((u,v)\in \mathcal{P}\). Such a subgraph is called a pairwise spanner with additive stretch \(\beta\). This paper discusses sparse pairwise spanners with additive stretches \(4\) and \(6\) and also the following special cases \(\mathcal{P}=S\times V\) and \(\mathcal{P}=S\times T\), where \(S\subseteq V\) and \(T\subseteq V\).
- $(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
- 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
- New pairwise spanners
- On Pairwise Spanners
- Small stretch pairwise spanners and approximate D-preservers
- Graphs with small additive stretch number
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- New (α, β) Spanners and Hopsets
- New additive spanners
- New results on linear size distance preservers
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
- Multi-priority graph sparsification
- Almost-optimal sublinear additive spanners
- Path-reporting distance oracles with linear size
- Graph spanners for group Steiner distances
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)
