# Approximating minimum cuts under insertions

Henzinger MH. 1995. Approximating minimum cuts under insertions. 22nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 944, 280–291.

Download

**No fulltext has been uploaded. References only!**

*Conference Paper*|

*Published*|

*English*

**Scopus indexed**

Author

Series Title

LNCS

Abstract

This paper presents insertions-only algorithms for maintaining the exact and approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact size k in time O(1) or O(log n) and a cut of size k in time linear in its size. The amortized time per insertion is O(1/ε 2) for a (2+ε)-approximation, O((log λ)((log n)/ε)2) for a (1+ε)-approximation, and O(λ log n) for the exact size of the minimum edge cut, where n is the number of nodes in the graph, λ is the size of the minimum cut and ε>0. The (2+ε)-approximation algorithm and the exact algorithm are deterministic, the (1+ε)-approximation algorithm is randomized. The algorithms are optimal in the sense that the time needed for m insertions matches the time needed by the best static algorithm on a m-edge graph. We also present a static 2-approximation algorithm for the size κ of the minimum vertex cut in a graph, which takes time O(n 2 min(√n,κ)). This is a factor of κ faster than the best algorithm for computing the exact size, which takes time O(κ 2 n 2 +κ 3 n 1.5). We give an insertionsonly algorithm for maintaining a (2+ε)-approximation of the minimum vertex cut with amortized insertion time O(n(logκk)/ε).

Publishing Year

Date Published

1995-07-01

Proceedings Title

22nd International Colloquium on Automata, Languages and Programming

Volume

944

Page

280–291

Conference

ICALP: International Colloquium on Automata, Languages, and Programming

Conference Location

Szeged, Hungary

Conference Date

1995-07-10 – 1995-07-14

ISBN

ISSN

eISSN

IST-REx-ID

### Cite this

Henzinger MH. Approximating minimum cuts under insertions. In:

*22nd International Colloquium on Automata, Languages and Programming*. Vol 944. Springer Nature; 1995:280–291. doi:10.1007/3-540-60084-1_81Henzinger, M. H. (1995). Approximating minimum cuts under insertions. In

*22nd International Colloquium on Automata, Languages and Programming*(Vol. 944, pp. 280–291). Szeged, Hungary: Springer Nature. https://doi.org/10.1007/3-540-60084-1_81Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.” In

*22nd International Colloquium on Automata, Languages and Programming*, 944:280–291. Springer Nature, 1995. https://doi.org/10.1007/3-540-60084-1_81.M. H. Henzinger, “Approximating minimum cuts under insertions,” in

*22nd International Colloquium on Automata, Languages and Programming*, Szeged, Hungary, 1995, vol. 944, pp. 280–291.Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.”

*22nd International Colloquium on Automata, Languages and Programming*, vol. 944, Springer Nature, 1995, pp. 280–291, doi:10.1007/3-540-60084-1_81.