2020/11/02 by Monika Henzinger, Pan Peng, Henzinger, Monika +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2011.00977
openalex publication_date 2020/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(W2 log W/ε3) worst-case update time, which is O(1) if both W and ε are constants. Note that there is a lower bound by Patrascu and Demaine (SIAM J. Comput. 2006) which shows that it takes Ω(log n) time per operation to maintain the exact weight of an MSF that holds even in the unweighted case, i.e. for W=1. We further show that any deterministic data structure that dynamically maintains the (1+ε)-approximate weight of an MSF requires super constant time per operation, if W≥ (log n)ωn(1). (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. This implies a randomized algorithm with worst-case o(log n) update time, whenever W=min\O((m^*)1/6/log2/3 n), 2^o(log n)\ and ε is constant. We complement this result by showing that for any constant ε,α>0 and W=nα, any (randomized) data structure that dynamically maintains the weight of an MSF of a graph G with edge weights in [1,W] and W = Ω(ε m^*) within a multiplicative factor of (1+ε) takes Ω(log n) time per operation.