New Results on Linear Size Distance Preservers
From MaRDI portal
Publication:5858650
DOI10.1137/19M123662XMaRDI QIDQ5858650
Publication date: 14 April 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1605.01106
Related Items (2)
Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Multi-priority graph sparsification
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new proof of the graph removal lemma
- Extremal problems in discrete geometry
- The convex hull of the integer points in a large ball
- Thorup-Zwick emulators are universally optimal hopsets
- New pairwise spanners
- An improved construction of progression-free sets
- Terminal embeddings
- Dual Failure Resilient BFS Structure
- Sparse Fault-Tolerant BFS Trees
- Graph removal lemmas
- On Pairwise Spanners
- Very Sparse Additive Spanners and Emulators
- Sparse Sourcewise and Pairwise Distance Preservers
- Small Stretch Pairwise Spanners and Approximate $D$-Preservers
- Error Amplification for Pairwise Spanner Lower Bounds
- Better Distance Preservers and Additive Spanners
- A Hierarchy of Lower Bounds for Sublinear Additive Spanners
- The 4/3 Additive Spanner Exponent Is Tight
- Testing subgraphs in large graphs
- A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
- Multiple Source Dual Fault Tolerant BFS Trees
- Distance-Preserving Subgraphs of Interval Graphs
- Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
- On the Structure of Unique Shortest Paths in Graphs
- Low Distortion Spanners
- Sparse Distance Preservers and Additive Spanners
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
This page was built for publication: New Results on Linear Size Distance Preservers