@article{11756,
  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.},
  author       = {Henzinger, Monika H and Peng, Pan},
  issn         = {0890-5401},
  journal      = {Information and Computation},
  number       = {12},
  publisher    = {Elsevier},
  title        = {{Constant-time dynamic weight approximation for minimum spanning forest}},
  doi          = {10.1016/j.ic.2021.104805},
  volume       = {281},
  year         = {2021},
}

