Average-case analysis of dynamic graph algorithms
Alberts D, Henzinger MH. 1998. Average-case analysis of dynamic graph algorithms. Algorithmica. 20, 31–60.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Alberts, D.;
Henzinger, MonikaISTA
Abstract
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.
Keywords
Publishing Year
Date Published
1998-01-01
Journal Title
Algorithmica
Publisher
Springer Nature
Acknowledgement
The authors would like to thank Emo Welzl for helpful discussions.
Volume
20
Page
31-60
ISSN
eISSN
IST-REx-ID
Cite this
Alberts D, Henzinger MH. Average-case analysis of dynamic graph algorithms. Algorithmica. 1998;20:31-60. doi:10.1007/pl00009186
Alberts, D., & Henzinger, M. H. (1998). Average-case analysis of dynamic graph algorithms. Algorithmica. Springer Nature. https://doi.org/10.1007/pl00009186
Alberts, D., and Monika H Henzinger. “Average-Case Analysis of Dynamic Graph Algorithms.” Algorithmica. Springer Nature, 1998. https://doi.org/10.1007/pl00009186.
D. Alberts and M. H. Henzinger, “Average-case analysis of dynamic graph algorithms,” Algorithmica, vol. 20. Springer Nature, pp. 31–60, 1998.
Alberts D, Henzinger MH. 1998. Average-case analysis of dynamic graph algorithms. Algorithmica. 20, 31–60.
Alberts, D., and Monika H. Henzinger. “Average-Case Analysis of Dynamic Graph Algorithms.” Algorithmica, vol. 20, Springer Nature, 1998, pp. 31–60, doi:10.1007/pl00009186.