Source-wise round-trip spanners

DOI10.1016/j.ipl.2017.04.009zbMath1416.05272OpenAlexW2608700661MaRDI QIDQ2628274

Chun Jiang Zhu, Kam-Yiu Lam

Publication date: 13 June 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.04.009

zbMATH Keywords

graph spannersgraph algorithmsshortest distanceround-trip spanners

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Deterministic improved round-trip spanners ⋮ On the VC-dimension of unique round-trip shortest path systems ⋮ Graph spanners: a tutorial review ⋮ A fast algorithm for source-wise round-trip spanners

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On sparse spanners of weighted graphs
• Low distortion spanners
• New Pairwise Spanners
• On Pairwise Spanners
• Additive spanners and (α, β)-spanners
• Sparse Sourcewise and Pairwise Distance Preservers
• Spanners and emulators with sublinear distance errors
• Additive Spanners in Nearly Quadratic Time
• Graph spanners
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• Compact roundtrip routing in directed networks (extended abstract)
• The 4/3 additive spanner exponent is tight
• Automata, Languages and Programming
• New Additive Spanners