  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.
  Similar to Alon et al., our dynamic low-stretch tree algorithm employs a
dynamic hierarchy of low-diameter decompositions (LDDs). As a major building
block we use a dynamic LDD that we obtain by adapting the random-shift
clustering of Miller et al. [SPAA 2013] to the dynamic setting. The major
technical challenge in our approach is to control the propagation of updates
within our hierarchy of LDDs: each update to one level of the hierarchy could
potentially induce several insertions and deletions to the next level of the
hierarchy. We achieve this goal by a sophisticated amortization approach.
  We believe that the dynamic random-shift clustering might be useful for
independent applications. One of these applications is the dynamic spanner
problem. By combining the random-shift clustering with the recent spanner
construction of Elkin and Neiman [SODA 2017]. We obtain a fully dynamic
algorithm for maintaining a spanner of stretch $ 2k - 1 $ and size $ O (n^{1 +
1/k} \log{n}) $ with amortized update time $ O (k \log^2 n) $ for any integer $
2 \leq k \leq \log n $. Compared to the state-of-the art in this regime
[Baswana et al. TALG '12], we improve upon the size of the spanner and the
update time by a factor of $ k $.
