Dynamic low-stretch trees via dynamic low-diameter decompositions

DOI10.1145/3313276.3316381zbMATH Open1433.68639arXiv1804.04928OpenAlexW3101090353MaRDI QIDQ5212779FDOQ5212779

Authors: Sebastian Forster, Gramoz Goranci 

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: 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}logn)$ with amortized update time $O(klo{g}^{2}n)$ for any integer $2leqkleqlogn$. 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$.

Full work available at URL: https://arxiv.org/abs/1804.04928

Recommendations

• Dynamic Low-Stretch Spanning Trees in Subpolynomial Time
• Minimizing diameters of dynamic trees
• Dynamic Trees with Almost-Optimal Access Cost
• Dynamic algorithms for graphs of bounded treewidth
• Dynamic algorithms for graphs of bounded treewidth
• On the treewidth of dynamic graphs
• On the treewidth of dynamic graphs
• On low tree-depth decompositions
• Distributed algorithms for low stretch spanning trees
• Lower-Stretch Spanning Trees

zbMATH Keywords

spannerlow-diameter decompositionlow-stretch tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cited In (5)

• Lower-Stretch Spanning Trees
• Minimizing diameters of dynamic trees
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Removing additive structure in 3SUM-based reductions

This page was built for publication: Dynamic low-stretch trees via dynamic low-diameter decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212779)