A fast algorithm for source-wise round-trip spanners
From MaRDI portal
Publication:2034785
DOI10.1016/j.tcs.2021.05.019OpenAlexW3164304453MaRDI QIDQ2034785
Song Han, Chun Jiang Zhu, Kam-Yiu Lam
Publication date: 23 June 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.05721
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On sparse spanners of weighted graphs
- Size-estimation framework with applications to transitive closure and reachability
- Graph spanners: a tutorial review
- Deterministic improved round-trip spanners
- Source-wise round-trip spanners
- New Pairwise Spanners
- On Pairwise Spanners
- Additive spanners and (α, β)-spanners
- Sparse Sourcewise and Pairwise Distance Preservers
- Approximate distance oracles
- Spanners and emulators with sublinear distance errors
- Additive Spanners in Nearly Quadratic Time
- Graph spanners
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Linear Size Distance Preservers
- An O(nm) time algorithm for finding the min length directed cycle in a graph
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Roundtrip spanners and roundtrip routing in directed graphs
- Constructing Light Spanners Deterministically in Near-Linear Time
- Constant girth approximation for directed graphs in subquadratic time
- Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
- Compact roundtrip routing in directed networks (extended abstract)
- Small Stretch Pairwise Spanners
- The 4/3 additive spanner exponent is tight
- Routing under balance
- Automata, Languages and Programming
- New Additive Spanners
This page was built for publication: A fast algorithm for source-wise round-trip spanners
