Constant-time dynamic weight approximation for minimum spanning forest
Henzinger MH, Peng P. 2021. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. 281(12), 104805.
Download (ext.)
https://arxiv.org/abs/2011.00977
[Preprint]
Journal Article
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Peng, Pan
Abstract
We give two fully dynamic algorithms that maintain a (1 + ε)-approximation of the weight M of a minimum spanning forest (MSF) of an n-node graph G with edges weights in [1, W ], for any ε > 0. (1) Our deterministic algorithm takes O (W 2 log W /ε3) worst-case update time, which is O (1) if both W and ε are constants. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case O (log W /ε4) update time if W = O ((m∗)1/6/log2/3 n), where m∗ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement our algorithmic results with two cell-probe lower bounds for dynamically maintaining an approximation of the weight of an MSF of a graph.
Publishing Year
Date Published
2021-12-01
Journal Title
Information and Computation
Publisher
Elsevier
Volume
281
Issue
12
Article Number
104805
ISSN
IST-REx-ID
Cite this
Henzinger MH, Peng P. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. 2021;281(12). doi:10.1016/j.ic.2021.104805
Henzinger, M. H., & Peng, P. (2021). Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2021.104805
Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.” Information and Computation. Elsevier, 2021. https://doi.org/10.1016/j.ic.2021.104805.
M. H. Henzinger and P. Peng, “Constant-time dynamic weight approximation for minimum spanning forest,” Information and Computation, vol. 281, no. 12. Elsevier, 2021.
Henzinger MH, Peng P. 2021. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. 281(12), 104805.
Henzinger, Monika H., and Pan Peng. “Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.” Information and Computation, vol. 281, no. 12, 104805, Elsevier, 2021, doi:10.1016/j.ic.2021.104805.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2011.00977