Maintaining the 4-edge-connected components of a graph on-line
Efim Dinitz · 2002
Two vertices v and u of an undirected graph are called k-edge-connected if there exist k edge-disjoint paths between v and u. The equivalence classes of this relation are called the k-edge-connected components. The author suggests graph structures and an incremental algorithm to maintain k-edge-connected components for the case k=4. Any sequence of a q queries Same-k-Component? and updates Insert-Edge on an n-vertex graph can be performed in O(q sigma (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/sup 2/n log(n/k)) preprocessing.>