# Technical Report CS0915

 TR#: CS0915 Class: CS Title: A $2$-level cactus tree model for the system of minimum and minimum+1 edge cuts of a graph and its incremental maintenance Authors: Yefim Dinitz and Zeev Nutov PDF CS0915.pdf Abstract: The known cactus tree model represents the minimum edge cuts of a graph in a clear and compact way and is used in related studies. We generalize this model to represent the minimum and minimum+1 edge cuts; for this purpose, we use new tools for modeling connectivity structures. The obtained representations are different for $\lambda$ odd and even; their size is linear in the number of vertices of the graph. Let $\lambda$ denote the cardinality of a minimum edge cut. We suggest efficient algorithms for the maintenance of our representations, and, thus, of the $(\lambda+2)$-connectivity classes of vertices (called also $(\lambda+2)$-components'') in an arbitrary graph undergoing insertions of edges. The time complexity of those algorithms, for $\lambda$ odd and even, is the same as achieved previously for the cases $\lambda=1$ and $2$, respectively. 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/CS0915), rather than to the URL of the PDF files directly. The latter URLs may change without notice.