TY - CONF
AB - 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].
AU - Henzinger, Monika H
AU - Poutré, Han
ID - 11805
SN - 0302-9743
T2 - 3rd Annual European Symposium on Algorithms
TI - Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
VL - 979
ER -