Publication Details
Title: Approximating Minimum Cuts Under Insertion
Author: M. R. Henzinger
Group: ICSI Technical Reports
Date: November 1994
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-063.pdf
Overview:
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. Keywords: dynamic graph algorithms, data structures, analysis and design of algorithms
Bibliographic Information:
ICSI Technical Report TR-94-063
Bibliographic Reference:
M. R. Henzinger. Approximating Minimum Cuts Under Insertion. ICSI Technical Report TR-94-063, November 1994
Author: M. R. Henzinger
Group: ICSI Technical Reports
Date: November 1994
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-063.pdf
Overview:
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. Keywords: dynamic graph algorithms, data structures, analysis and design of algorithms
Bibliographic Information:
ICSI Technical Report TR-94-063
Bibliographic Reference:
M. R. Henzinger. Approximating Minimum Cuts Under Insertion. ICSI Technical Report TR-94-063, November 1994