Seminar • Algorithms and Complexity — Dynamic Low-Stretch Trees via Dynamic Low-Diameter DecompositionsExport this event to calendar

Wednesday, March 6, 2019 1:30 PM EST

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.

Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2024 (80)
    1. April (8)
    2. March (22)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)