@book{4612,
  editor       = {Alur, Rajeev and Henzinger, Thomas A and Sontag, Eduardo D},
  isbn         = {978-3-540-61155-4},
  issn         = {0302-9743},
  pages        = {IX, 619},
  publisher    = {Springer},
  title        = {{Hybrid Systems III: Verification and Control}},
  doi          = {10.1007/BFb0020931},
  volume       = {1066},
  year         = {1996},
}

@inproceedings{11805,
  abstract     = {In this paper, we present sparse certificates for biconnectivity together with algorithms for updating these certificates. We thus obtain fully-dynamic algorithms for biconnectivity in graphs that run in O(√n log n log⌈m/n⌉) amortized time per operation, where m is the number of edges and n is the number of nodes in the graph. This improves upon the results in [11], in which algorithms were presented running in O(√m) amortized time, and solves the open problem to find certificates to speed up biconnectivity, as stated in [2].},
  author       = {Henzinger, Monika H and Poutré, Han},
  booktitle    = {3rd Annual European Symposium on Algorithms},
  isbn         = {9783540603139},
  issn         = {1611-3349},
  location     = {Corfu, Greece},
  pages        = {171–184},
  publisher    = {Springer Nature},
  title        = {{Certificates and fast algorithms for biconnectivity in fully-dynamic graphs}},
  doi          = {10.1007/3-540-60313-1_142},
  volume       = {979},
  year         = {1995},
}

@inproceedings{11806,
  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)/ε).},
  author       = {Henzinger, Monika H},
  booktitle    = {22nd International Colloquium on Automata, Languages and Programming},
  isbn         = {9783540494256},
  issn         = {1611-3349},
  location     = {Szeged, Hungary},
  pages        = {280–291},
  publisher    = {Springer Nature},
  title        = {{Approximating minimum cuts under insertions}},
  doi          = {10.1007/3-540-60084-1_81},
  volume       = {944},
  year         = {1995},
}