MAINTAINING BRIDGE-CONNECTED AND BICONNECTED COMPONENTS ONLINE

We consider the twin problems of maintaining the bridge-connected comp onents and the biconnected components of a dynamic undirected graph. T he allowed changes to the graph are vertex and edge insertions. We giv e an algorithm for each problem. With simple data structures, each alg orithm runs in O(n log n + m) time, where n is the number of vertices and m is the number of operations. We develop a modified version of th e dynamic trees of Sleator and Tarjan that is suitable for efficient r ecursive algorithms, and use it to reduce the running time of the algo rithms for both problems to O(m-alpha(m, n)), where alpha is a functio nal inverse of Ackermann's function. This time bound is optimal. All o f the algorithms use O(n) space.