A fast algorithm for source-wise round-trip spanners
From MaRDI portal
Publication:2034785
DOI10.1016/J.TCS.2021.05.019OpenAlexW3164304453MaRDI QIDQ2034785FDOQ2034785
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximate distance oracles
- Low distortion spanners
- On sparse spanners of weighted graphs
- Graph spanners
- Automata, Languages and Programming
- Additive spanners and (Ξ±, Ξ²)-spanners
- Sparse Sourcewise and Pairwise Distance Preservers
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- New Additive Spanners
- Size-estimation framework with applications to transitive closure and reachability
- On Pairwise Spanners
- Graph spanners: a tutorial review
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Spanners and emulators with sublinear distance errors
- New Pairwise Spanners
- Small Stretch Pairwise Spanners
- Additive Spanners in Nearly Quadratic Time
- Bypassing ErdΕsβ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
- The 4/3 additive spanner exponent is tight
- Roundtrip spanners and roundtrip routing in directed graphs
- Compact roundtrip routing in directed networks (extended abstract)
- Deterministic improved round-trip spanners
- Source-wise round-trip spanners
- Linear Size Distance Preservers
- An O(nm) time algorithm for finding the min length directed cycle in a graph
- Constructing Light Spanners Deterministically in Near-Linear Time
- Constant girth approximation for directed graphs in subquadratic time
- Routing under balance
Cited In (4)
Recommendations
- Title not available (Why is that?) π π
- Title not available (Why is that?) π π
- Approximation algorithms for quickest spanning tree problems π π
- Algorithms β ESA 2004 π π
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t π π
- Approximation algorithms for somek-source shortest paths spanning tree problems π π
- Roundtrip spanners and roundtrip routing in directed graphs π π
- Deterministic improved round-trip spanners π π
- Efficient and Simple Algorithms for Fault-Tolerant Spanners π π
- Fast Constructions of Light-Weight Spanners for General Graphs π π
This page was built for publication: A fast algorithm for source-wise round-trip spanners
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034785)
