@inproceedings{11834,
  abstract     = {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].

We 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.},
  author       = {Goranci, Gramoz and Henzinger, Monika H and Thorup, Mikkel},
  booktitle    = {24th Annual European Symposium on Algorithms},
  isbn         = {978-3-95977-015-6},
  issn         = {1868-8969},
  location     = {Aarhus, Denmark},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Incremental exact min-cut in poly-logarithmic amortized update time}},
  doi          = {10.4230/LIPICS.ESA.2016.46},
  volume       = {57},
  year         = {2016},
}

@inproceedings{11835,
  abstract     = {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.

In 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.

We 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.},
  author       = {Henzinger, Monika H and Neumann, Stefan},
  booktitle    = {24th Annual European Symposium on Algorithms},
  isbn         = {978-3-95977-015-6},
  issn         = {1868-8969},
  location     = {Aarhus, Denmark},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Incremental and fully dynamic subgraph connectivity for emergency planning}},
  doi          = {10.4230/LIPICS.ESA.2016.48},
  volume       = {57},
  year         = {2016},
}