SRC Technical Note 1997-020
SRC Technical Note 1997-020We 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 previously best deterministic algorithms were O(min {m^{2/3},n}) in general graphs and O(sqrt n) in plane graphs for fully dynamic biconnectivity. We improve these running times to O(sqrt(m) log n) in general graphs and O(log ^2 n) in plane graphs. Our algorithm for general graphs can also find the biconnected components of all vertices in time O(n).
Back to the SRC Technical Notes main page.