@inproceedings{11802,
  abstract     = {In this paper we survey algorithmic aspects of Web information retrieval. As an example, we discuss ranking of search engine results using connectivity analysis.},
  author       = {Henzinger, Monika H},
  booktitle    = {8th Annual European Symposium on Algorithms},
  isbn         = {9783540410041},
  issn         = {1611-3349},
  location     = {Saarbrücken, Germany},
  pages        = {1–8},
  publisher    = {Springer Nature},
  title        = {{Web information retrieval - an algorithmic perspective}},
  doi          = {10.1007/3-540-45253-2_1},
  volume       = {1879},
  year         = {2000},
}

@inproceedings{11803,
  abstract     = {We present the first fully dynamic algorithm for maintaining a minimum spanning tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and, bipartiteness in amortized time O(n 1/3 log n) per update, with O(1) worst case time per query.},
  author       = {Henzinger, Monika H and King, Valerie},
  booktitle    = {24th International Colloquium on Automata, Languages and Programming},
  isbn         = {9783540631651},
  issn         = {1611-3349},
  location     = {Bologna, Italy},
  pages        = {594–604},
  publisher    = {Springer Nature},
  title        = {{Maintaining minimum spanning trees in dynamic graphs}},
  doi          = {10.1007/3-540-63165-8_214},
  volume       = {1256},
  year         = {1997},
}

@inproceedings{11804,
  abstract     = {This paper shows how a general technique, called lock-step search, used in dynamic graph algorithms, can be used to improve the running time of two problems arising in program verification and communication protocol design.
(1)We consider the nonemptiness problem for Streett automata: We are given a directed graph G = (V, E) with n = ¦V¦ and m = ¦E¦, and a collection of pairs of subsets of vertices, called Streett pairs,〈L i , U i 〉, i = 1.k. The question is whether G has a cycle (not necessarily simple) which, for each 1 ≤ i ≤ k, if it contains a vertex from L i then it also contains a vertex of U i . Let b=Σ i=1..k |L i |+|U i |. The previously best algorithm takes time O((m + b) min{n, k}). We present an algorithm that takes time 𝑂(𝑚min{𝑚𝑙𝑜𝑔𝑛,‾‾‾‾‾‾√𝑘,𝑛}+𝑏𝑚𝑖𝑛{𝑙𝑜𝑔𝑛,𝑘}).
(2)In communication protocol pruning we are given a directed graph G = (V, E) with l special vertices. The problem is to efficiently maintain the strongly-connected components of the special vertices on a restricted set of edge deletions. Let m i be the number of edges in the strongly connected component of the ith special vertex. The previously best algorithm repeatedly recomputes the strongly-connected components which leads to a running time of O(Σ i m 2i). We present an algorithm with time 𝑂(𝑙√∑𝑖𝑚1.5𝑖).},
  author       = {Henzinger, Monika H and Telle, Jan Arne},
  booktitle    = {5th Scandinavian Workshop on Algorithm Theory},
  isbn         = {9783540614227},
  issn         = {1611-3349},
  location     = {Reykjavik, Iceland},
  pages        = {16–27},
  publisher    = {Springer Nature},
  title        = {{Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning}},
  doi          = {10.1007/3-540-61422-2_117},
  volume       = {1097},
  year         = {1996},
}

@inproceedings{11910,
  abstract     = {We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms.

For the dynamic connectivity problem the previously best randomized algorithm takes expected time O(log3 n) per update, amortized over Ω(m) updates. Using the new sampling lemma, we improve its running time to O(log2 n). There exists a lower bound in the cell probe model for the time per operation of Ω(log n/ log log n) for this problem.

Similarly improved running times are achieved for 2-edge connectivity, k-weight minimum spanning tree, and bipartiteness.},
  author       = {Henzinger, Monika H and Thorup, Mikkel},
  booktitle    = {23rd International Colloquium on Automata, Languages, and Programming},
  isbn         = {9783540614401},
  issn         = {1611-3349},
  location     = {Paderborn, Germany},
  pages        = {290--299},
  publisher    = {Springer Nature},
  title        = {{Improved sampling with applications to dynamic graph algorithms}},
  doi          = {10.1007/3-540-61440-0_136},
  volume       = {1099},
  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},
}