@inproceedings{11805,
  abstract     = {In this paper, we present sparse certificates for biconnectivity together with algorithms for updating these certificates. We thus obtain fully-dynamic algorithms for biconnectivity in graphs that run in O(√n log n log⌈m/n⌉) amortized time per operation, where m is the number of edges and n is the number of nodes in the graph. This improves upon the results in [11], in which algorithms were presented running in O(√m) amortized time, and solves the open problem to find certificates to speed up biconnectivity, as stated in [2].},
  author       = {Henzinger, Monika H and Poutré, Han},
  booktitle    = {3rd Annual European Symposium on Algorithms},
  isbn         = {9783540603139},
  issn         = {1611-3349},
  location     = {Corfu, Greece},
  pages        = {171–184},
  publisher    = {Springer Nature},
  title        = {{Certificates and fast algorithms for biconnectivity in fully-dynamic graphs}},
  doi          = {10.1007/3-540-60313-1_142},
  volume       = {979},
  year         = {1995},
}