| 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 |
| 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.
To the list of the CS technical reports of 1997
To the main CS technical reports page