The authors present a technique for designing fully dynamic algorithms with polylogarithmic time per operation for dynamically testing several graph properties. The technique combines a new graph decomposition and randomization. The edges are partitioned into O ( log n ) levels in such a way that the edges from loosely connected parts are on higher levels than the edges from highly connected parts. For each level i, a forest is maintained with edges in levels j ≤ i . After deleting an edge on level i, the edges on level i are sampled to find with high probability an edge that reconnects the two subtrees or to learn, also with high probability, that the cut defined by the deleted edge is too sparse for level i. In the latter case, the edges on the cut are copied to the next level and the procedure is tried for this higher level.
This technique is applied first to design a fully dynamic connectivity algorithm for which the amortized cost of update is O ( log3 n ) . This is also the cost of the algorithm for testing biconnectivity. The connectivity algorithm is then adapted to yield other algorithms. They include an algorithm to maintain a minimum spanning tree with k different weights in O ( p k log3 n ) time for p updates and an algorithm that, for a graph with weights between 1 and u, solves the 1 + &egr; -approximation of the minimum spanning tree problem in O ( ( p log3 n log u )&egr; ) amortized time for p updates.
