---
_id: '11928'
abstract:
- lang: eng
  text: "We present a model with restricted randomness for edge updates in dynamic
    graph algorithms and a general technique\r\nfor 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 maximum cardinality matching, minimum spanning
    forest, connectivity, 2-edge connectivity,\r\nk-edge connectivity, k-vertex connectivity,
    and bipartiteness. Given a random graph G with mo edges and n vertices and\r\na
    sequence of 1 update operations such that the graph contains rni edges after operation
    i, the expected time for performing the updates for any 1 is O(1 logn + n xi=,
    l/fii) in the case of minimum spanning forests, connectivity, 2-\r\nedge connectivity,
    and bipartiteness. The expected time per update operation is O(n) in the case
    of maximum matching. For k-edge and k-vertex connectivity we also give improved
    bounds. Additionally we give an insertions-only algorithm for maximum cardinality
    matching with worst-case O(n) amortized time per insertion. "
article_processing_charge: No
author:
- first_name: David
  full_name: Alberts, David
  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.
    In: <i>6th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial
    and Applied Mathematics; 1995:312-321.'
  apa: 'Alberts, D., &#38; Henzinger, M. H. (1995). Average case analysis of dynamic
    graph algorithms. In <i>6th Annual ACM-SIAM Symposium on Discrete Algorithms</i>
    (pp. 312–321). San Francisco, CA, United States: Society for Industrial and Applied
    Mathematics.'
  chicago: Alberts, David, and Monika H Henzinger. “Average Case Analysis of Dynamic
    Graph Algorithms.” In <i>6th Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    312–21. Society for Industrial and Applied Mathematics, 1995.
  ieee: D. Alberts and M. H. Henzinger, “Average case analysis of dynamic graph algorithms,”
    in <i>6th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, San Francisco,
    CA, United States, 1995, pp. 312–321.
  ista: 'Alberts D, Henzinger MH. 1995. Average case analysis of dynamic graph algorithms.
    6th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete
    Algorithms, 312–321.'
  mla: Alberts, David, and Monika H. Henzinger. “Average Case Analysis of Dynamic
    Graph Algorithms.” <i>6th Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    Society for Industrial and Applied Mathematics, 1995, pp. 312–21.
  short: D. Alberts, M.H. Henzinger, in:, 6th Annual ACM-SIAM Symposium on Discrete
    Algorithms, Society for Industrial and Applied Mathematics, 1995, pp. 312–321.
conference:
  end_date: 1995-01-24
  location: San Francisco, CA, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 1995-01-22
date_created: 2022-08-19T07:10:23Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2023-02-21T16:24:58Z
day: '01'
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://dl.acm.org/doi/10.5555/313651.313712
month: '01'
oa: 1
oa_version: Published Version
page: 312-321
publication: 6th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  isbn:
  - '0898713498'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
  record:
  - id: '11680'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Average case analysis of dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1995'
...