Files

Abstract

We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs. A fully dynamic algorithm maintains a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edges and n be the number of vertices in a graph. The time per operation of the best deterministic algorithms is O(sqrt(n)) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(minm2/3, n) in general graphs and O(sqrt(n)) in plane graphs for fully dynamic biconnectivity. We improve the later running times to O(sqrt(m.log(n)) in general graphs and O(log2 n) in plane graphs. Our algorithm for general graphs can also find the biconnected components of all vertices in time O(n).

Details

PDF