Approximating Minimum Cuts Under Insertion

TitleApproximating Minimum Cuts Under Insertion
Publication TypeTechnical Report
Year of Publication1994
AuthorsHenzinger, M. Rauch
Other Numbers933
Keywordsanalysis and design of algorithms, data structures, dynamic graph algorithms
Abstract

This paper presents insertions-only algorithms for maintaining the exact and approximate size of the minimum edge and vertex cut of a graph. The algorithms are optimal in the sense that they match the performance of the best static algorithm for the problem. We first give an incremental algorithm that maintains a (2+?)-approximation of the size minimum edge cut in amortized time O(1/?^2) per insertion and O(1) per query. Next we show how to maintain the exact size ? of the minimum edge cut in amortized time O(? log n) per operation. Combining these algorithms with random sampling finally gives a randomized Monte-Carlo algorithm that maintains a (1+?)-approximation of the minimum edge cut in amortized time O((log ?) ((log n)/?)^2) per insertion.Finally we present the first 2-approximation algorithm for the size ? of the minimum vertex cut in a graph. It takes time O(n^2 min (?n, ?)). This is an improvement of a factor of ? over the time for the best algorithm for computing the exact size of the minimum vertex cut, which takes time ?^2 n^2 + k^3 n^{1.5}). We also give the first algorithm for maintaining a (2+?)-approximation of the minimum vertex cut under insertions. Its amortized insertion time is O(n /?). The algorithms output the approximate or exact size k in constant time and a cut of size k in time linear in its size.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-063.pdf
Bibliographic Notes

ICSI Technical Report TR-94-063

Abbreviated Authors

M. R. Henzinger

ICSI Publication Type

Technical Report