---
_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 M. 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. (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 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. Henzinger, “Average-case analysis of dynamic graph algorithms,”
    <i>Algorithmica</i>, vol. 20. Springer Nature, pp. 31–60, 1998.
  ista: Alberts D, Henzinger M. 1998. Average-case analysis of dynamic graph algorithms.
    Algorithmica. 20, 31–60.
  mla: Alberts, D., and Monika 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. Henzinger, Algorithmica 20 (1998) 31–60.
date_created: 2022-07-28T06:50:51Z
date_published: 1998-01-01T00:00:00Z
date_updated: 2024-11-06T12:26:40Z
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'
...