research-article

Dynamic low-stretch trees via dynamic low-diameter decompositions

Authors:

Sebastian Forster,

Gramoz GoranciAuthors Info & Claims

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

Pages 377 - 388

https://doi.org/10.1145/3313276.3316381

Published: 23 June 2019 Publication History

Get Access

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. In particular, we give a bound on the number of changes made to the LDD per update to the input graph that is significantly better than the trivial bound implied by the update time.

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 (k log² n) for any integer 2 ≤ k ≤ logn . Compared to the state-of-the art in this regime Baswana et al. [TALG 2012], we improve upon the size of the spanner and the update time by a factor of k .

References

[1]

Ittai Abraham, Yair Bartal, and Ofer Neiman. 2008. Nearly Tight Low Stretch Spanning Trees. In Symposium on Foundations of Computer Science (FOCS). 781– 790.

Abstract

References

Cited By

Index Terms

Recommendations

Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs

Compact Distance Oracles with Large Sensitivity and Low Stretch

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Get Access

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations