Paper Info
Title
Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs
Abstract
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. p n log n logd m ne/ 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 [12], in which algorithms were presented running in O. p m log n/ amortized time, and solves the open problem to find certificates to speed up biconnectivity, as stated in [2].
Year
DOI
Venue
1995
10.1007/3-540-60313-1_142
ESA
Keywords
Field
DocType
fully-dynamic graphs,fast algorithms
Discrete mathematics,Binary logarithm,Graph,Combinatorics,Open problem,Computer science,Amortized analysis,Algorithm,Speedup
Conference
ISBN
Citations 
PageRank 
3-540-60313-1
13
1.58
References 
Authors
11
2
Name
Order
Citations
PageRank
Monika Rauch Henzinger14307481.86
Johannes A. La Poutré230824.78