Dynamic minimum spanning forest with subpolynomial worst-case update time

DOI10.1109/FOCS.2017.92MaRDI QIDQ6946294zbMATH OpenFDO

Authors Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2017.92

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(11)

• Negative-weight single-source shortest paths in near-linear time
• Maximum flow and minimum-cost flow in almost-linear time
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Fully-adaptive dynamic connectivity of square intersection graphs
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Worst-case to expander-case reductions: derandomized and generalized
• Practical expander decomposition
• On maximal k-edge-connected subgraphs of undirected graphs
• Tree-packing revisited: faster fully dynamic min-cut and arboricity
• Faster dynamic 2-edge connectivity in directed graphs
• Length-constrained directed expander decomposition and length-constrained vertex-capacitated flow shortcuts

This page was built for publication: Dynamic minimum spanning forest with subpolynomial worst-case update time

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