Dynamic Connectivity and Minimum Spanning Forest
Farah Chanchary
In this talk, I will present a deterministic fully dynamic algorithm for connectivity and how this structure can be expanded to maintain the minimum spanning forest of any graph. The amortized results - $O(\log^2 n)$ update time for connectivity and $O(\log^4 n)$ update time for minimum spanning forest - are due to Holm et al. (2001).