Almost-optimal sublinear additive spanners

DOI10.1145/3564246.3585125MaRDI QIDQ6499230zbMATH OpenFDO

Authors Zihan Tan, Tianyi Zhang

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585125

zbMATH Keywords

additive spannersshortest paths

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A hierarchy of lower bounds for sublinear additive spanners
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Better distance preservers and additive spanners
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• scientific article; zbMATH DE number 3869331 (Why is no real title available?)
• Low distortion spanners
• Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
• New additive spanners
• New pairwise spanners
• On sparse spanners of weighted graphs
• Spanners and emulators with sublinear distance errors
• Sparse Sourcewise and Pairwise Distance Preservers
• The 4/3 additive spanner exponent is tight
• Very sparse additive spanners and emulators

Cited in

(2)

• Additive spanner lower bounds with optimal inner graph structure
• Lightweight near-additive spanners

This page was built for publication: Almost-optimal sublinear additive spanners

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