Technical Report CS0921

TR#:CS0921
Class:CS
Title: The general structure of edge-connectivity of a vertex subset in a graph and its incremental maintenance . Odd case
Authors: Yefim Dinitz and Alek Vainshtein
PDFCS0921.pdf
Abstract: Let $G=(V,E)$ be an undirected graph, $S$ be a subset of its vertices, ${\frak C}_S$ be the set of minimum edge-cuts partitioning $S$, $\lambda_S$ be the cardinality of such a cut. We suggest a graph structure, called the {\it connectivity carcass\/} of $S$, that represents both cuts in $\frak C_S$ and the partition of $V$ by all these cuts; its size is $O(\min\{|E|,\lambda_S|V|\})$. In this paper we present general constructions and study in detail the case $\lambda_S$ odd; the specifics of the case $\lambda_S$ even are considered elsewhere. For an adequate description of the connectivity carcass we introduce a new type of graphs: locally orientable graphs, which generalize digraphs. The connectivity carcass consists of a locally orientable quotient graph of $G$, a cactus tree (in case $\lambda_S$ odd, just a tree) representing all distinct partitions of $S$ by cuts in ${\frak C}_S$, and a mapping connecting them. One can build it in $O(|S|)$ max-flow computations in $G$. For an arbitrary sequence of $u$ edge insertions not changing $\lambda_S$, the connectivity carcass can be maintained in time $O(|V|\min\{|E|,\lambda_S|V|\}+u)$. For two vertices of $G$, queries asking whether they are separated by a cut in $\frak C_S$ are answered in $O(1)$ worst-case time per query. Another possibility is to maintain the carcass in $O(|S|\min\{|E|,\lambda_S|V|\}+u)$ time, but to answer the queries in $O(1)$ time only if at least one of the vertices belongs to $S$.
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/1997/CS/CS0921), 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 1997
To the main CS technical reports page

Computer science department, Technion
admin