Exploring unknown environments
S. Albers, M.H. Henzinger, SIAM Journal on Computing 29 (2000) 1164–1188.

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