- Series
- ACO Student Seminar
- Time
- Friday, March 16, 2018 - 1:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Gramoz Goranci – CS, University of Vienna – gramoz.goranci@gmail.com – https://sites.google.com/view/ggoranci/
- Organizer
- He Guo

A low-diameter decomposition (LDD) of an undirected graph G is a partitioning of G into components of bounded diameter, such that only a small fraction of original edges are between the components. This decomposition has played instrumental role
in the design of low-stretch spanning tree, spanners, distributed algorithms etc.
A natural question is whether such a decomposition can be efficiently maintained/updated as G undergoes insertions/deletions of edges. We make the first step towards answering this question by designing a fully-dynamic graph algorithm that maintains an
LDD in sub-linear update time.
It is known that any undirected graph G admits a spanning tree T with nearly logarithmic average stretch, which can be computed in nearly linear-time. This tree decomposition underlies many recent progress in static algorithms for combinatorial and scientific
flows. Using our dynamic LDD algorithm, we present the first non-trivial algorithm that dynamically maintains a low-stretch spanning tree in \tilde{O}(t^2) amortized update time, while achieving (t + \sqrt{n^{1+o(1)}/t}) stretch, for every 1 \leq t \leq n.
Joint work with Sebastian Krinninger.