|
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(5log,) 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 mortid tim O(dog X)(dog) /)) pr insertion. Finally we present the first 2-approximation algorithm for the size of the minimum vertex cut in a graph. It takes time O(rz2 min(,)). 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 O(2n 2 + k3nl'). We also give the first algorithm for maintaining a (2 + e)-approximation of the minimum vertex cut under insertions. Its amortized insertion time is O(n/e). The algorithms output the approximate or exact size k in constant time and a cut of size k in time linear in its size., |
