Fully Dynamic Algorithms for 2-Edge Connectivity
Zvi Galil, Giuseppe Francesco Italiano · SIAM Journal on Computing · 1992
This paper studies the problem of maintaining the 2-edge-connected components of a graph undergoing repeated dynamic modifications, such as edge insertions and edge deletions. It is shown how to test at any time whether two vertices belong to the same 2-edge-connected component, and how to insert and delete an edge in $O(m^{2/3} )$ time in the worst case, where m is the current number of edges in the graph. This answers a question posed by Westbrook and Tarjan [Tech. Report CS-TR-229-89, Dept. of Computer Science, Princeton University, Princeton, NJ, August 1989; Algorithmica., to appear]. For planar graphs, the paper presents algorithms that support all these operations in $O(\sqrt {n\log \log n} )$ worst-case time each, where n is the total number of vertices in the graph.