An Improved Randomized Data Structure for Dynamic Graph Connectivity

Understand

We present a randomized algorithm for dynamic graph connectivity.

• With failure probability less than $1/n^c$ (for any constant $c$ we choose), our solution has worst case running time $O(\log^3 n)$ per edge insertion, $O(\log^4 n)$ per edge deletion, and $O(\log n/\log\log n)$ per query, where $n$ is the number of vertices.
• The previous best algorithm has worst case running time $O(\log^4 n)$ per edge insertion and $O(\log^5 n)$ per edge deletion.
• The improvement is made by reducing the randomness used in the previous result, so that we save a $\log n$ factor in update time.