---
res:
bibo_abstract:
- "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. @eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: David
foaf_name: Alberts, David
foaf_surname: Alberts
- foaf_Person:
foaf_givenName: Monika H
foaf_name: Henzinger, Monika H
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
orcid: 0000-0002-5008-6530
dct_date: 1995^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0898713498
dct_language: eng
dct_publisher: Society for Industrial and Applied Mathematics@
dct_title: Average case analysis of dynamic graph algorithms@
...