TR#:  CS0774 
Class:  CS 
Title:  MAINTAINING THE 4EDGECONNECTED COMPONENTS
OF A GRAPH ONLINE. 
Authors:  E. Dinitz 
CS0774.pdf  
Abstract: 
Two vertices v and u of an undirected graph are called kedgeconnected if there exists k edgedisjoint paths between v and u. The equivalence classes of this relation are called the kedgeconnected components. We suggest graph structures and an incremental algorithm to maintain kedgeconnected components for the case k = 4. Any sequence of q queries SamekComponent? and updates InsertEdge on an nvertex 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 kedgeconnected components (k arbitrary) in a (k1)edgeconnected graph is presented. The complexity is O((q+n)\alpha(q,n)), with O(m+k^2 n \log(n/k)) preprocessing.

Copyright  The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information 
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgibin/trinfo.cgi/1993/CS/CS0774), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1993
To the main CS technical reports page