Maintaining the 3-Edge-Connected Components of a Graph On-Line
Zvi Galil, Giuseppe Francesco Italiano · SIAM Journal on Computing · 1993
The problem of maintaining the 3-edge-connected components of a graph undergoing repeated dynamic modifications, such as edge and vertex insertions, is studied. This paper shows how to answer the question of whether or not two vertices belong to the same 3-edge-connected component of a connected graph that is undergoing only edge insertions. Any sequence of q query and updates on an n-vertex graph can be performed in $O((n + q)\alpha (q,n))$ time.