Dynamic low-stretch trees via dynamic low-diameter decompositions
Sebastian Forster, Gramoz Goranci · 2019
Spanning trees of low average stretch on the non-tree edges, as introduced by Alon et al. [SICOMP 1995], are a natural graph-theoretic object. In recent years, they have found significant applications in solvers for symmetric diagonally dominant (SDD) linear systems. In this work, we provide the first dynamic algorithm for maintaining such trees under edge insertions and deletions to the input graph. Our algorithm has update time n1/2 + o(1) and the average stretch of the maintained tree is no(1) , which matches the stretch in the seminal result of Alon et al.