Maintaining minimum spanning trees in dynamic graphs LNCS Henzinger, Monika H ; https://orcid.org/0000-0002-5008-6530 King, Valerie We present the first fully dynamic algorithm for maintaining a minimum spanning tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1/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(n 1/3 log n) per update, with O(1) worst case time per query. Springer Nature 1997 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text https://research-explorer.ista.ac.at/record/11803 Henzinger M, King V. Maintaining minimum spanning trees in dynamic graphs. In: <i>24th International Colloquium on Automata, Languages and Programming</i>. Vol 1256. Springer Nature; 1997:594–604. doi:<a href="https://doi.org/10.1007/3-540-63165-8_214">10.1007/3-540-63165-8_214</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1007/3-540-63165-8_214 info:eu-repo/semantics/altIdentifier/issn/0302-9743 info:eu-repo/semantics/altIdentifier/e-issn/1611-3349 info:eu-repo/semantics/altIdentifier/isbn/9783540631651 info:eu-repo/semantics/altIdentifier/e-isbn/9783540691945 info:eu-repo/semantics/closedAccess