Technical Report CS0804

TR#:CS0804
Class:CS
Title: THE GENERAL STRUCTURE OF EDGE-CONNECTIVITY OF A VERTEX SUBSET IN A GRAPH AND ITS INCREMENTAL MAINTENANCE.
Authors: Ye. Dinitz and A. Vainshtein
PDFNot Available
Abstract:

Let G=(V,E) be an undirected graph, S be a subset of its vertices, {\Cal C}_S be the set of minimum edge-cuts partitioning S. We suggest a graph structure, called the connectivity carcass of S, that represents both cuts in {\Cal C}_S and the partition of V by all these cuts. An adequate description of the connectivity carcass is provided in terms of the two types of graphs: locally orientable graphs, which generalize digraphs, and cacti, which generalize trees. The connectivity carcass consists of a locally orientable quotient graph of G, a cactus representing all distinct partitions of S by cuts in {\Cal C}_S, and a mapping connecting them. One can build it in |S|-1 max-flow computations in G. For an arbitrary sequence of u edge insertions not changing the size of k of a cut in {\Cal C}_S, the connectivity carcass can be maintained in time O(\Min \{|V| \Cdot |E|, K|V|^2\}+U \Alpha (U,|V|)). For two vertices of G, queries asking whether they are separated by a cut in {\Cal C}_S are answered in O(\Alpha,(A,|V|)) amortized time per query, where q is the number of queries; such a cut itself is shown in O(|V|) amortized time. The dag representation of all cuts in {\Cal C}_S separating two given vertices in S is obtained in O(\Min \{|E|, K|V|\}) amortized time.

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/1994/CS/CS0804), 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 1994
To the main CS technical reports page

Computer science department, Technion
admin