Better Distance Preservers and Additive Spanners

DOI10.1145/3490147MaRDI QIDQ5035880zbMATH OpenOpenAlexFDO

Authors Greg Bodwin, Virginia Vassilevska Williams

Publication date 22 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.05599

zbMATH Keywords

distance preserversspannerssparsification

Mathematics Subject Classification ID

Distance in graphs (05C12) Computer science (68-XX)

Recommendations

• Better distance preservers and additive spanners
• scientific article; zbMATH DE number 2079365
• Small stretch pairwise spanners and approximate D-preservers
• Sparse Distance Preservers and Additive Spanners
• Linear size distance preservers

Cited in

(4)

• A note on distance-preserving graph sparsification
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Additive spanner lower bounds with optimal inner graph structure
• Path-reporting distance oracles with linear size

This page was built for publication: Better Distance Preservers and Additive Spanners

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