---
_id: '11806'
abstract:
- lang: eng
  text: 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)/ε).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: 'Henzinger M. Approximating minimum cuts under insertions. In: <i>22nd International
    Colloquium on Automata, Languages and Programming</i>. Vol 944. Springer Nature;
    1995:280–291. doi:<a href="https://doi.org/10.1007/3-540-60084-1_81">10.1007/3-540-60084-1_81</a>'
  apa: 'Henzinger, M. (1995). Approximating minimum cuts under insertions. In <i>22nd
    International Colloquium on Automata, Languages and Programming</i> (Vol. 944,
    pp. 280–291). Szeged, Hungary: Springer Nature. <a href="https://doi.org/10.1007/3-540-60084-1_81">https://doi.org/10.1007/3-540-60084-1_81</a>'
  chicago: Henzinger, Monika. “Approximating Minimum Cuts under Insertions.” In <i>22nd
    International Colloquium on Automata, Languages and Programming</i>, 944:280–291.
    Springer Nature, 1995. <a href="https://doi.org/10.1007/3-540-60084-1_81">https://doi.org/10.1007/3-540-60084-1_81</a>.
  ieee: M. Henzinger, “Approximating minimum cuts under insertions,” in <i>22nd International
    Colloquium on Automata, Languages and Programming</i>, Szeged, Hungary, 1995,
    vol. 944, pp. 280–291.
  ista: 'Henzinger M. 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.'
  mla: Henzinger, Monika. “Approximating Minimum Cuts under Insertions.” <i>22nd International
    Colloquium on Automata, Languages and Programming</i>, vol. 944, Springer Nature,
    1995, pp. 280–291, doi:<a href="https://doi.org/10.1007/3-540-60084-1_81">10.1007/3-540-60084-1_81</a>.
  short: M. Henzinger, in:, 22nd International Colloquium on Automata, Languages and
    Programming, Springer Nature, 1995, pp. 280–291.
conference:
  end_date: 1995-07-14
  location: Szeged, Hungary
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 1995-07-10
date_created: 2022-08-11T14:17:33Z
date_published: 1995-07-01T00:00:00Z
date_updated: 2024-11-06T08:23:27Z
day: '01'
doi: 10.1007/3-540-60084-1_81
extern: '1'
intvolume: '       944'
language:
- iso: eng
month: '07'
oa_version: None
page: 280–291
publication: 22nd International Colloquium on Automata, Languages and Programming
publication_identifier:
  eisbn:
  - '9783540600848'
  eissn:
  - 1611-3349
  isbn:
  - '9783540494256'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Approximating minimum cuts under insertions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 944
year: '1995'
...