David Alberts, Monika Rauch Henzinger: Average-Case Analysis of Dynamic Graph Algorithms. Algorithmica 20(1): 31-60 (1998)