Average-case analysis of dynamic graph algorithms
D. Alberts, M. Henzinger, Algorithmica 20 (1998) 31–60.