Donald Bren School of Information and Computer Sciences

In previous work we introduced sparsification, a technique that transforms fully dynamic algorithms for sparse graphs into ones that work on any graph, with a logarithmic increase in complexity. In this work we describe an improvement on this technique that avoids the logarithmic overhead. Using our improved sparsification technique, we keep track of the following properties: minimum spanning forest, best swap, connectivity, 2-edge-connectivity, and bipartiteness, in time O(n^1/2) per edge insertion or deletion; 2-vertex-connectivity and 3-vertex-connectivity, in time O(n) per update; and 4-vertex-connectivity, in time O(na(n)) per update.