---
_id: '11680'
abstract:
- lang: eng
  text: '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.'
acknowledgement: The authors would like to thank Emo Welzl for helpful discussions.
article_processing_charge: No
article_type: original
author:
- first_name: D.
  full_name: Alberts, D.
  last_name: Alberts
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: Alberts D, Henzinger MH. Average-case analysis of dynamic graph algorithms.
    <i>Algorithmica</i>. 1998;20:31-60. doi:<a href="https://doi.org/10.1007/pl00009186">10.1007/pl00009186</a>
  apa: Alberts, D., &#38; Henzinger, M. H. (1998). Average-case analysis of dynamic
    graph algorithms. <i>Algorithmica</i>. Springer Nature. <a href="https://doi.org/10.1007/pl00009186">https://doi.org/10.1007/pl00009186</a>
  chicago: Alberts, D., and Monika H Henzinger. “Average-Case Analysis of Dynamic
    Graph Algorithms.” <i>Algorithmica</i>. Springer Nature, 1998. <a href="https://doi.org/10.1007/pl00009186">https://doi.org/10.1007/pl00009186</a>.
  ieee: D. Alberts and M. H. Henzinger, “Average-case analysis of dynamic graph algorithms,”
    <i>Algorithmica</i>, vol. 20. Springer Nature, pp. 31–60, 1998.
  ista: Alberts D, Henzinger MH. 1998. Average-case analysis of dynamic graph algorithms.
    Algorithmica. 20, 31–60.
  mla: Alberts, D., and Monika H. Henzinger. “Average-Case Analysis of Dynamic Graph
    Algorithms.” <i>Algorithmica</i>, vol. 20, Springer Nature, 1998, pp. 31–60, doi:<a
    href="https://doi.org/10.1007/pl00009186">10.1007/pl00009186</a>.
  short: D. Alberts, M.H. Henzinger, Algorithmica 20 (1998) 31–60.
date_created: 2022-07-28T06:50:51Z
date_published: 1998-01-01T00:00:00Z
date_updated: 2023-02-21T16:33:27Z
day: '01'
doi: 10.1007/pl00009186
extern: '1'
intvolume: '        20'
keyword:
- Dynamic graph algorithm
- Average-case analysis
- Minimum spanning forest
- Connectivity
- Bipartiteness
- Maximum matching.
language:
- iso: eng
month: '01'
oa_version: None
page: 31-60
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11928'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Average-case analysis of dynamic graph algorithms
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 20
year: '1998'
...
---
_id: '11681'
abstract:
- lang: eng
  text: 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.
acknowledgement: .
article_processing_charge: No
article_type: original
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: M. L.
  full_name: Fredman, M. L.
  last_name: Fredman
citation:
  ama: Henzinger MH, Fredman ML. Lower bounds for fully dynamic connectivity problems
    in graphs. <i>Algorithmica</i>. 1998;22(3):351-362. doi:<a href="https://doi.org/10.1007/pl00009228">10.1007/pl00009228</a>
  apa: Henzinger, M. H., &#38; Fredman, M. L. (1998). Lower bounds for fully dynamic
    connectivity problems in graphs. <i>Algorithmica</i>. Springer Nature. <a href="https://doi.org/10.1007/pl00009228">https://doi.org/10.1007/pl00009228</a>
  chicago: Henzinger, Monika H, and M. L. Fredman. “Lower Bounds for Fully Dynamic
    Connectivity Problems in Graphs.” <i>Algorithmica</i>. Springer Nature, 1998.
    <a href="https://doi.org/10.1007/pl00009228">https://doi.org/10.1007/pl00009228</a>.
  ieee: M. H. Henzinger and M. L. Fredman, “Lower bounds for fully dynamic connectivity
    problems in graphs,” <i>Algorithmica</i>, vol. 22, no. 3. Springer Nature, pp.
    351–362, 1998.
  ista: Henzinger MH, Fredman ML. 1998. Lower bounds for fully dynamic connectivity
    problems in graphs. Algorithmica. 22(3), 351–362.
  mla: Henzinger, Monika H., and M. L. Fredman. “Lower Bounds for Fully Dynamic Connectivity
    Problems in Graphs.” <i>Algorithmica</i>, vol. 22, no. 3, Springer Nature, 1998,
    pp. 351–62, doi:<a href="https://doi.org/10.1007/pl00009228">10.1007/pl00009228</a>.
  short: M.H. Henzinger, M.L. Fredman, Algorithmica 22 (1998) 351–362.
date_created: 2022-07-28T06:58:36Z
date_published: 1998-11-01T00:00:00Z
date_updated: 2022-09-12T09:03:36Z
day: '01'
doi: 10.1007/pl00009228
extern: '1'
intvolume: '        22'
issue: '3'
keyword:
- Dynamic planarity testing
- Dynamic connectivity testing
- Lower bounds
- Cell probe model
language:
- iso: eng
month: '11'
oa_version: None
page: 351-362
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds for fully dynamic connectivity problems in graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '1998'
...