Gramoz Goranci, University of Vienna
Spanning
trees
of
low
average
stretch
on
the
non-tree
edges
are
natural graph-theoretic
objects
that
have
found
applications
in
fast
solvers
for symmetric
diagonally
dominant
(SDD)
linear
systems,
construction
of competitive
oblivious
routing
schemes
and
approximation
algorithms.
In
this
talk,
I
will
present
the
first
non-trivial
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.
[SICOMP'
95].
The
key
ingredients
to our
result
are
(1)
dynamic
maintenance
of
low-diameter
decompositions (LLDs),
(2)
controlling
the
propagation
of
updates
within
a
hierarchy
of dynamic
LDDs, and
(3)
incorporation
of
dynamic
cut
sparsifiers
to
improve the
update
time.
This
is
joint
work
with
Sebastian
Forster,
and
will
appear
at
STOC
2019.