@inproceedings{11910,
  abstract     = {We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms.

For the dynamic connectivity problem the previously best randomized algorithm takes expected time O(log3 n) per update, amortized over Ω(m) updates. Using the new sampling lemma, we improve its running time to O(log2 n). There exists a lower bound in the cell probe model for the time per operation of Ω(log n/ log log n) for this problem.

Similarly improved running times are achieved for 2-edge connectivity, k-weight minimum spanning tree, and bipartiteness.},
  author       = {Henzinger, Monika H and Thorup, Mikkel},
  booktitle    = {23rd International Colloquium on Automata, Languages, and Programming},
  isbn         = {9783540614401},
  issn         = {1611-3349},
  location     = {Paderborn, Germany},
  pages        = {290--299},
  publisher    = {Springer Nature},
  title        = {{Improved sampling with applications to dynamic graph algorithms}},
  doi          = {10.1007/3-540-61440-0_136},
  volume       = {1099},
  year         = {1996},
}