Technical Report CS0915

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
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.
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 (, 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