Constant-time dynamic weight approximation for minimum spanning forest

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 / log 2 / 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.

Authors

• Monika Henzinger
• Pan Peng

Keywords

• Dynamic graph algorithms
• Minimum spanning forest
• Sublinear-time algorithms
• Cell-probe lower bounds