conference paper published yes Monika H Henzinger author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530 Valerie King author ICALP: International Colloquium on Automata, Languages, and Programming 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 Nature1997Bologna, Italy eng 0302-9743 1611-3349 978354063165110.1007/3-540-63165-8_214 1256594–604 yes Henzinger M, King V. 1997. Maintaining minimum spanning trees in dynamic graphs. 24th International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 1256, 594–604. Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Trees in Dynamic Graphs.” <i>24th International Colloquium on Automata, Languages and Programming</i>, vol. 1256, Springer Nature, 1997, pp. 594–604, doi:<a href="https://doi.org/10.1007/3-540-63165-8_214">10.1007/3-540-63165-8_214</a>. Henzinger, M., &#38; King, V. (1997). Maintaining minimum spanning trees in dynamic graphs. In <i>24th International Colloquium on Automata, Languages and Programming</i> (Vol. 1256, pp. 594–604). Bologna, Italy: Springer Nature. <a href="https://doi.org/10.1007/3-540-63165-8_214">https://doi.org/10.1007/3-540-63165-8_214</a> M. Henzinger and V. King, “Maintaining minimum spanning trees in dynamic graphs,” in <i>24th International Colloquium on Automata, Languages and Programming</i>, Bologna, Italy, 1997, vol. 1256, pp. 594–604. Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Trees in Dynamic Graphs.” In <i>24th International Colloquium on Automata, Languages and Programming</i>, 1256:594–604. Springer Nature, 1997. <a href="https://doi.org/10.1007/3-540-63165-8_214">https://doi.org/10.1007/3-540-63165-8_214</a>. 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> M. Henzinger, V. King, in:, 24th International Colloquium on Automata, Languages and Programming, Springer Nature, 1997, pp. 594–604. 118032022-08-11T13:35:06Z2024-11-06T12:13:35Z