"Fully Dynamic 2-Edge Connectivity Algorithm in Polylogarithmic 
Time per Operation"
Monika Rauch Henzinger and Valerie King
Note #1997-004a. June 27, 1997. 18 pages.

This paper presents the first dynamic algorithm that maintains 2-edge
connectivity in polylogarithmic time per operation.  The algorithm is
a Las-Vegas type randomized algorithm.

The expected time for p = Omega(m + n) insertions or deletions of edges
is O(p log^5n), where m is the number of edges in the initial graph
with n nodes.  The worst-case time for a query is O(log n).  If only
deletions are allowed then the cost for p updates is O(p log^4 n)
expected time.