Dynamic low-stretch trees via dynamic low-diameter decompositions

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 n 1/2 + o (1) and the average stretch of the maintained tree is n o (1) , which matches the stretch in the seminal result of Alon et al.

Authors

• Sebastian Forster
• Gramoz Goranci

Keywords

• low-diameter decomposition
• low-stretch tree
• spanner