Dynamic Low-Stretch Spanning Trees in Subpolynomial Time

DOI10.1137/1.9781611975994.28MaRDI QIDQ5146794zbMATH OpenOpenAlexFDO

Authors Shiri Chechik, Tianyi Zhang

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975994.28

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(5)

• Dynamic low-stretch trees via dynamic low-diameter decompositions
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Negative-weight single-source shortest paths in near-linear time
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Near-optimal directed low-diameter decompositions

This page was built for publication: Dynamic Low-Stretch Spanning Trees in Subpolynomial Time

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