---
_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: *6th Annual ACM-SIAM Symposium on Discrete Algorithms*. Society for Industrial
and Applied Mathematics; 1995:312-321.'
apa: 'Alberts, D., & Henzinger, M. H. (1995). Average case analysis of dynamic
graph algorithms. In *6th Annual ACM-SIAM Symposium on Discrete Algorithms*
(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 *6th Annual ACM-SIAM Symposium on Discrete Algorithms*,
312–21. Society for Industrial and Applied Mathematics, 1995.
ieee: D. Alberts and M. H. Henzinger, “Average case analysis of dynamic graph algorithms,”
in *6th Annual ACM-SIAM Symposium on Discrete Algorithms*, 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.” *6th Annual ACM-SIAM Symposium on Discrete Algorithms*,
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'
...