{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:17Z","timestamp":1787337617704,"version":"build-2736575974"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>\n                    We present the first fully dynamic algorithm for maintaining a minimum spanning forest in time $o(\\sqrt n)$ per operation. To be precise, the algorithm uses O(n\n                    <jats:sup>1\/3<\/jats:sup>\n                    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\n                    <jats:sup>1\/3<\/jats:sup>\n                    log n) per update, with O(1) worst case time per query.\n                  <\/jats:p>","DOI":"10.1137\/s0097539797327209","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"364-374","source":"Crossref","is-referenced-by-count":46,"title":["Maintaining Minimum Spanning Forests in Dynamic Graphs"],"prefix":"10.1137","volume":"31","author":[{"given":"Monika R.","family":"Henzinger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valerie","family":"King","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"T. Cormen, C. Leiserson, and R. Rivest,\n                      Introduction to Algorithms\n                      , MIT Press, Cambridge, MA, 1989, pp. 381\u2013399."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574030"},{"key":"R3","unstructured":"D. Eppstein, Z. Galil, and G. F. Italiano,\n                      Improved Sparsification\n                      , Tech. Report 93\u201020, Department of Information and Computer Science, University of California, Irvine, CA."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"T. Feder and M. Mihail,\n                      Balanced matroids\n                      , in Proceedings of the 24th ACM Symposium on Theory of Computing, ACM Press, New York, 1992, pp. 26\u201338.","DOI":"10.1145\/129712.129716"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0218008"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Monika Henzinger, Mikkel Thorup, Improved sampling with applications to dynamic graph algorithms, Lecture Notes in Comput. Sci., Vol. 1099, Springer, Berlin, 1996, 290\u201329998f:68214","DOI":"10.1007\/3-540-61440-0_136"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69672-5"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539797327209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:21:17Z","timestamp":1787336477000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539797327209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539797327209"],"URL":"https:\/\/doi.org\/10.1137\/s0097539797327209","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}