Maintaining minimum spanning trees in dynamic graphs

Monika Rauch Henzinger and Valerie King
Proc. 24th Int. Coll. Automata, Languages, and Programming (ICALP 1997), Lecture Notes in Computer Science 1256, Pierpaolo Degano, Roberto Gorrieri, and Alberto Marchetti Spaccamela, ed., Springer-Verlag, Jul 1997, pp. 594–604
SIAM J. Computing 31(2):364–374, Oct 2001
Tech. report DCS-251-IR, Univ. of Victoria, Computer Science Dept., 1997

Cites:

• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Improved sparsification
• Sparsification — A technique for speeding up dynamic graph algorithms