@article{11680,
  abstract     = {We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1) it allows restrictions on the set of edges which can be used for insertions and (2) the type (insertion or deletion) of each update operation is arbitrary, i.e., not random. We use our technique to analyze existing and new dynamic algorithms for the following problems: maximum cardinality matching, minimum spanning forest, connectivity, 2-edge connectivity, k -edge connectivity, k -vertex connectivity, and bipartiteness. Given a random graph G with m 0 edges and n vertices and a sequence of l update operations such that the graph contains m i edges after operation i , the expected time for performing the updates for any l is O(llogn+∑li=1n/m−−√i) in the case of minimum spanning forests, connectivity, 2-edge connectivity, and bipartiteness. The expected time per update operation is O(n) in the case of maximum matching. We also give improved bounds for k -edge and k -vertex connectivity. Additionally we give an insertions-only algorithm for maximum cardinality matching with worst-case O(n) amortized time per insertion.},
  author       = {Alberts, D. and Henzinger, Monika H},
  issn         = {1432-0541},
  journal      = {Algorithmica},
  keywords     = {Dynamic graph algorithm, Average-case analysis, Minimum spanning forest, Connectivity, Bipartiteness, Maximum matching.},
  pages        = {31--60},
  publisher    = {Springer Nature},
  title        = {{Average-case analysis of dynamic graph algorithms}},
  doi          = {10.1007/pl00009186},
  volume       = {20},
  year         = {1998},
}

@article{11681,
  abstract     = {We prove lower bounds on the complexity of maintaining fully dynamic k -edge or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs. We show an amortized lower bound of Ω (log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model, where b is the word size of the machine and n is the number of vertices in G . We also show an amortized lower bound of Ω (log n /(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic connectivity problems.},
  author       = {Henzinger, Monika H and Fredman, M. L.},
  issn         = {1432-0541},
  journal      = {Algorithmica},
  keywords     = {Dynamic planarity testing, Dynamic connectivity testing, Lower bounds, Cell probe model},
  number       = {3},
  pages        = {351--362},
  publisher    = {Springer Nature},
  title        = {{Lower bounds for fully dynamic connectivity problems in graphs}},
  doi          = {10.1007/pl00009228},
  volume       = {22},
  year         = {1998},
}