Additive spanner lower bounds with optimal inner graph structure

DOI10.4230/LIPICS.ICALP.2024.28MaRDI QIDQ6875180zbMATH OpenFDO

Authors Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein

Publication date 14 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2024.28

zbMATH Keywords

additive spannersgraph theory

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A hierarchy of lower bounds for sublinear additive spanners
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• All-Pairs Almost Shortest Paths
• Almost-optimal sublinear additive spanners
• Better Distance Preservers and Additive Spanners
• Better lower bounds for shortcut sets and additive spanners via an improved alternation product
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• scientific article; zbMATH DE number 2079397 (Why is no real title available?)
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• Low distortion spanners
• New additive emulators
• New additive spanner lower bounds by an unlayered obstacle product
• New additive spanners
• On sparse spanners of weighted graphs
• Simple linear-size additive emulators
• Simpler and higher lower bounds for shortcut sets
• Sparse Distance Preservers and Additive Spanners
• Sparse Sourcewise and Pairwise Distance Preservers
• The 4/3 additive spanner exponent is tight
• The convex hull of the integer points in a large ball
• Very sparse additive spanners and emulators

This page was built for publication: Additive spanner lower bounds with optimal inner graph structure

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