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 PDF CS0921.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$. 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/1997/CS/CS0921), rather than to the URL of the PDF files directly. The latter URLs may change without notice.