Technical Report CS0871

TR#:CS0871
Class:CS
Title: MAINTAINING THE CLASSES OF 4-EDGE-CONNECTIVITY IN A GRAPH ON-LINE.
Authors: Ye. Dinitz and J. Westbrook
PDFNot Available
Abstract: Two vertices of an undirected graph are called k-edge-connected if there exist $k$ edge-disjoint paths between them (equivalently: they cannot be disconnected by the removal of less than $K$ edges from the graph). Equivalence classes of this relation are called classes of $k$-edge-connectivity, or $k$-edge connected components. This paper describes graph structures relevant to classes of 4-edge-connectivity and traces their transformations as new edges are inserted into the graph. Data structures and an algorithm to maintain incrementally these classes are given. Starting with the empty graph, any sequence of {\em q Same-4-Class?} queries and {\em n Insert-Vertex} and {\em m Insert-Edge} updates can be performed in $O(q+m+n \log n)$ total time. Each individual query requires $O(1)$ time in the worst-case. In addition, an algorithm for maintaining the classes of k-edge-connectivity ($k$ arbitrary) in a $(k-1)$-edge-connected graph is presented. Its complexity is $O(q+m+n)$, with $O(M+k^2 n \log(n/k))$ preprocessing, where $M$ is the number of edges initially in the graph and $n$ is the number of its vertices. This algorithm is extended to handle the case of $k$ increasing under augmentation.
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/1995/CS/CS0871), 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 1995
To the main CS technical reports page

Computer science department, Technion
admin