Maintaining minimum spanning forests in dynamic graphs
Henzinger M, King V. 2001. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 31(2), 364–374.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA 
;
King, Valerie
;
King, ValerieAbstract
We present the first fully dynamic algorithm for maintaining a minimum spanning forest in time 𝑜(𝑛√) per operation. To be precise, the algorithm uses O(n1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and bipartiteness in amortized time O(n1/3 log n) per update, with O(1) worst case time per query.
Publishing Year
Date Published
2001-03-01
Journal Title
SIAM Journal on Computing
Publisher
Society for Industrial & Applied Mathematics
Volume
31
Issue
2
Page
364-374
ISSN
eISSN
IST-REx-ID
Cite this
Henzinger M, King V. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 2001;31(2):364-374. doi:10.1137/s0097539797327209
Henzinger, M., & King, V. (2001). Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/s0097539797327209
Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Forests in Dynamic Graphs.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2001. https://doi.org/10.1137/s0097539797327209.
M. Henzinger and V. King, “Maintaining minimum spanning forests in dynamic graphs,” SIAM Journal on Computing, vol. 31, no. 2. Society for Industrial & Applied Mathematics, pp. 364–374, 2001.
Henzinger M, King V. 2001. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 31(2), 364–374.
Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Forests in Dynamic Graphs.” SIAM Journal on Computing, vol. 31, no. 2, Society for Industrial & Applied Mathematics, 2001, pp. 364–74, doi:10.1137/s0097539797327209.
Google Scholar