Average Case Analysis of Dynamic Graph Algorithms
David Alberts
Institut für Informatik
Freie Universität Berlin
email: alberts@inf.fu-berlin.de
(joint work with Monika Rauch Henzinger)
Report B 95-03
März 1995
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-95-03.ps.gz
Average Case Analysis of Dynamic Graph Algorithms
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., {\em 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(l \log n + n \sum_{i=1}^{l}
1/\sqrt 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.