Deterministic improved round-trip spanners

DOI10.1016/J.IPL.2017.09.008MaRDI QIDQ2410583zbMATH OpenOpenAlexFDO

Authors Chun Jiang Zhu, Kam-Yiu Lam

Publication date 18 October 2017

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

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

zbMATH Keywords

graph algorithmsdeterministic algorithmsgraph spannersshortest distancesround-trip spanners

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 2119746
• Roundtrip spanners and roundtrip routing in directed graphs
• Source-wise round-trip spanners
• A fast algorithm for source-wise round-trip spanners
• Improved deterministic distributed construction of spanners

Cites work

• scientific article; zbMATH DE number 1305501 (Why is no real title available?)
• scientific article; zbMATH DE number 2119746 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Additive spanners in nearly quadratic time
• Approximate distance oracles
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• Compact roundtrip routing in directed networks (extended abstract)
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Graph spanners
• Low distortion spanners
• New additive spanners
• On sparse spanners of weighted graphs
• Source-wise round-trip spanners
• Spanners and emulators with sublinear distance errors
• The 4/3 additive spanner exponent is tight

Cited in

(6)

• Graph spanners: a tutorial review
• scientific article; zbMATH DE number 2119746 (Why is no real title available?)
• On the VC-dimension of unique round-trip shortest path systems
• Improved sourcewise roundtrip spanners with constant stretch
• Source-wise round-trip spanners
• A fast algorithm for source-wise round-trip spanners

This page was built for publication: Deterministic improved round-trip spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2410583)