|Title:|| MAINTAINING THE 4-EDGE-CONNECTED COMPONENTS
OF A GRAPH ON-LINE.
|Authors:|| E. Dinitz
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.
|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/cgi-bin/tr-info.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
Computer science department, Technion