Source-wise round-trip spanners

DOI10.1016/J.IPL.2017.04.009MaRDI QIDQ2628274zbMATH OpenOpenAlexFDO

Authors 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 algorithmsgraph spannersround-trip spannersshortest distance

Mathematics Subject Classification ID

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

Recommendations

• A fast algorithm for source-wise round-trip spanners
• scientific article; zbMATH DE number 2119746
• Roundtrip spanners and roundtrip routing in directed graphs
• Multipath spanners
• Network Flow Spanners
• Network flow spanners
• Deterministic improved round-trip spanners
• Spanners for directed transmission graphs
• Multipath spanners via fault-tolerant spanners
• Local routing in WSPD-based spanners

Cites work

• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Additive spanners in nearly quadratic time
• Automata, Languages and Programming
• 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
• 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?)
• Low distortion spanners
• New additive spanners
• New pairwise spanners
• On Pairwise Spanners
• On sparse spanners of weighted graphs
• Spanners and emulators with sublinear distance errors
• Sparse Sourcewise and Pairwise Distance Preservers
• Terminal embeddings
• The 4/3 additive spanner exponent is tight

Cited in

(5)

• 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
• Deterministic improved round-trip spanners
• Improved sourcewise roundtrip spanners with constant stretch

This page was built for publication: Source-wise round-trip spanners

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