---
_id: '11834'
abstract:
- lang: eng
  text: "We present a deterministic incremental algorithm for exactly maintaining
    the size of a minimum cut with ~O(1) amortized time per edge insertion and O(1)
    query time. This result partially answers an open question posed by Thorup [Combinatorica
    2007]. It also stays in sharp contrast to a polynomial conditional lower-bound
    for the fully-dynamic weighted minimum cut problem. Our algorithm is obtained
    by combining a recent sparsification technique of Kawarabayashi and Thorup [STOC
    2015] and an exact incremental algorithm of Henzinger [J. of Algorithm 1997].\r\n\r\nWe
    also study space-efficient incremental algorithms for the minimum cut problem.
    Concretely, we show that there exists an O(n log n/epsilon^2) space Monte-Carlo
    algorithm that can process a stream of edge insertions starting from an empty
    graph, and with high probability, the algorithm maintains a (1+epsilon)-approximation
    to the minimum cut. The algorithm has ~O(1) amortized update-time and constant
    query-time."
alternative_title:
- LIPIcs
article_number: '46'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
  full_name: Goranci, Gramoz
  last_name: Goranci
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Mikkel
  full_name: Thorup, Mikkel
  last_name: Thorup
citation:
  ama: 'Goranci G, Henzinger MH, Thorup M. Incremental exact min-cut in poly-logarithmic
    amortized update time. In: <i>24th Annual European Symposium on Algorithms</i>.
    Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2016.46">10.4230/LIPICS.ESA.2016.46</a>'
  apa: 'Goranci, G., Henzinger, M. H., &#38; Thorup, M. (2016). Incremental exact
    min-cut in poly-logarithmic amortized update time. In <i>24th Annual European
    Symposium on Algorithms</i> (Vol. 57). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPICS.ESA.2016.46">https://doi.org/10.4230/LIPICS.ESA.2016.46</a>'
  chicago: Goranci, Gramoz, Monika H Henzinger, and Mikkel Thorup. “Incremental Exact
    Min-Cut in Poly-Logarithmic Amortized Update Time.” In <i>24th Annual European
    Symposium on Algorithms</i>, Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2016. <a href="https://doi.org/10.4230/LIPICS.ESA.2016.46">https://doi.org/10.4230/LIPICS.ESA.2016.46</a>.
  ieee: G. Goranci, M. H. Henzinger, and M. Thorup, “Incremental exact min-cut in
    poly-logarithmic amortized update time,” in <i>24th Annual European Symposium
    on Algorithms</i>, Aarhus, Denmark, 2016, vol. 57.
  ista: 'Goranci G, Henzinger MH, Thorup M. 2016. Incremental exact min-cut in poly-logarithmic
    amortized update time. 24th Annual European Symposium on Algorithms. ESA: Annual
    European Symposium on Algorithms, LIPIcs, vol. 57, 46.'
  mla: Goranci, Gramoz, et al. “Incremental Exact Min-Cut in Poly-Logarithmic Amortized
    Update Time.” <i>24th Annual European Symposium on Algorithms</i>, vol. 57, 46,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2016.46">10.4230/LIPICS.ESA.2016.46</a>.
  short: G. Goranci, M.H. Henzinger, M. Thorup, in:, 24th Annual European Symposium
    on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
conference:
  end_date: 2016-08-24
  location: Aarhus, Denmark
  name: 'ESA: Annual European Symposium on Algorithms'
  start_date: 2016-08-22
date_created: 2022-08-12T10:58:32Z
date_published: 2016-08-18T00:00:00Z
date_updated: 2023-02-16T12:05:59Z
day: '18'
doi: 10.4230/LIPICS.ESA.2016.46
extern: '1'
external_id:
  arxiv:
  - '1611.06500'
intvolume: '        57'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ESA.2016.46
month: '08'
oa: 1
oa_version: Published Version
publication: 24th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - 978-3-95977-015-6
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Incremental exact min-cut in poly-logarithmic amortized update time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 57
year: '2016'
...
---
_id: '11835'
abstract:
- lang: eng
  text: "During the last 10 years it has become popular to study dynamic graph problems
    in a emergency planning or sensitivity setting: Instead of considering the general
    fully dynamic problem, we only have to process a single batch update of size d;
    after the update we have to answer queries.\r\n\r\nIn this paper, we consider
    the dynamic subgraph connectivity problem with sensitivity d: We are given a graph
    of which some vertices are activated and some are deactivated. After that we get
    a single update in which the states of up to $d$ vertices are changed. Then we
    get a sequence of connectivity queries in the subgraph of activated vertices.\r\n\r\nWe
    present the first fully dynamic algorithm for this problem which has an update
    and query time only slightly worse than the best decremental algorithm. In addition,
    we present the first incremental algorithm which is tight with respect to the
    best known conditional lower bound; moreover, the algorithm is simple and we believe
    it is implementable and efficient in practice."
alternative_title:
- LIPIcs
article_number: '48'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Stefan
  full_name: Neumann, Stefan
  last_name: Neumann
citation:
  ama: 'Henzinger MH, Neumann S. Incremental and fully dynamic subgraph connectivity
    for emergency planning. In: <i>24th Annual European Symposium on Algorithms</i>.
    Vol 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2016.48">10.4230/LIPICS.ESA.2016.48</a>'
  apa: 'Henzinger, M. H., &#38; Neumann, S. (2016). Incremental and fully dynamic
    subgraph connectivity for emergency planning. In <i>24th Annual European Symposium
    on Algorithms</i> (Vol. 57). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPICS.ESA.2016.48">https://doi.org/10.4230/LIPICS.ESA.2016.48</a>'
  chicago: Henzinger, Monika H, and Stefan Neumann. “Incremental and Fully Dynamic
    Subgraph Connectivity for Emergency Planning.” In <i>24th Annual European Symposium
    on Algorithms</i>, Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2016. <a href="https://doi.org/10.4230/LIPICS.ESA.2016.48">https://doi.org/10.4230/LIPICS.ESA.2016.48</a>.
  ieee: M. H. Henzinger and S. Neumann, “Incremental and fully dynamic subgraph connectivity
    for emergency planning,” in <i>24th Annual European Symposium on Algorithms</i>,
    Aarhus, Denmark, 2016, vol. 57.
  ista: 'Henzinger MH, Neumann S. 2016. Incremental and fully dynamic subgraph connectivity
    for emergency planning. 24th Annual European Symposium on Algorithms. ESA: Annual
    European Symposium on Algorithms, LIPIcs, vol. 57, 48.'
  mla: Henzinger, Monika H., and Stefan Neumann. “Incremental and Fully Dynamic Subgraph
    Connectivity for Emergency Planning.” <i>24th Annual European Symposium on Algorithms</i>,
    vol. 57, 48, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2016.48">10.4230/LIPICS.ESA.2016.48</a>.
  short: M.H. Henzinger, S. Neumann, in:, 24th Annual European Symposium on Algorithms,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
conference:
  end_date: 2016-08-24
  location: Aarhus, Denmark
  name: 'ESA: Annual European Symposium on Algorithms'
  start_date: 2016-08-22
date_created: 2022-08-12T11:05:41Z
date_published: 2016-08-18T00:00:00Z
date_updated: 2023-02-16T12:07:46Z
day: '18'
doi: 10.4230/LIPICS.ESA.2016.48
extern: '1'
external_id:
  arxiv:
  - '1611.05248'
intvolume: '        57'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ESA.2016.48
month: '08'
oa: 1
oa_version: Published Version
publication: 24th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - 978-3-95977-015-6
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Incremental and fully dynamic subgraph connectivity for emergency planning
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 57
year: '2016'
...