Technical Report CS0774

Two vertices v and u of an undirected graph are called k-edge-connected if there exists k edge-disjoint paths between v and u. The equivalence classes of this relation are called the k-edge-connected components. We suggest graph structures and an incremental algorithm to maintain k-edge-connected components for the case k = 4. Any sequence of q queries Same-k-Component? and updates Insert-Edge on an n-vertex graph can be performed in O(q \alpha(q,n) + n \log n) time, with O(m + n \log n) preprocessing (m is the number of edges in the initial graph). Besides, an algorithm for maintaining k-edge-connected components (k arbitrary) in a (k-1)-edge-connected graph is presented. The complexity is O((q+n)\alpha(q,n)), with O(m+k^2 n \log(n/k)) preprocessing.