Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs

Monika Rauch Henzinger, Johannes A. La PoutréESA 1995 · OpenReview

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].
BibTeX
@inproceedings{henzinger1995certificates,
  author = {Monika Rauch Henzinger and Johannes A. La Poutré},
  title = {{Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs}},
  booktitle = {ESA},
  year = {1995},
  url = {https://openreview.net/forum?id=DNVlxkyLh4},
}

Loading related content...

Figure