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

Lower bounds for fully dynamic connectivity problems in graphs
M. Henzinger, M.L. Fredman, Algorithmica 22 (1998) 351–362.