Technical Report CS0774

TR#:CS0774
Class:CS
Title: MAINTAINING THE 4-EDGE-CONNECTED COMPONENTS OF A GRAPH ON-LINE.
Authors: E. Dinitz
PDFCS0774.pdf
Abstract:

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.

CopyrightThe 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
admin