{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:43:48Z","timestamp":1792111428050,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":16,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_156","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:51:54Z","timestamp":1553097114000},"page":"802-805","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fully Dynamic Minimum Spanning Trees"],"prefix":"10.1007","author":[{"given":"Giuseppe F.","family":"Italiano","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"156_CR6351","doi-asserted-by":"crossref","unstructured":"Alberts D, Cattaneo G, Italiano GF (1997) An empirical study of dynamic graph algorithms. ACM J Exp Algorithm 2","DOI":"10.1145\/264216.264223"},{"key":"156_CR6352","doi-asserted-by":"crossref","unstructured":"Cattaneo G, Faruolo P, Ferraro Petrillo U, Italiano GF (2002) Maintaining dynamic minimum spanning trees: an experimental study. In: Proceeding 4th workshop on algorithm engineering and experiments (ALENEX 02), 6\u20138 Jan, pp 111\u2013125","DOI":"10.1007\/3-540-45643-0_9"},{"key":"156_CR6353","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF01994879","volume":"32","author":"D Eppstein","year":"1992","unstructured":"Eppstein D (1992) Finding the k smallest spanning trees. BIT 32:237\u2013248","journal-title":"BIT"},{"key":"156_CR6354","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1142\/S0218195994000136","volume":"4","author":"D Eppstein","year":"1994","unstructured":"Eppstein D (1994) Tree-weighted neighbors and geometric k smallest spanning trees. Int J Comput Geom Appl 4:229\u2013238","journal-title":"Int J Comput Geom Appl"},{"issue":"5","key":"156_CR6355","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D Eppstein","year":"1997","unstructured":"Eppstein D, Galil Z, Italiano GF, Nissenzweig A (1997) Sparsification \u2013 a technique for speeding up dynamic graph algorithms. J Assoc Comput Mach 44(5):669\u2013696","journal-title":"J Assoc Comput Mach"},{"key":"156_CR6356","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","volume":"13","author":"D Eppstein","year":"1992","unstructured":"Eppstein D, Italiano GF, Tamassia R, Tarjan RE, Westbrook J, Yung M (1992) Maintenance of a minimum spanning forest in a dynamic plane graph. J Algorithms 13:33\u201354","journal-title":"J Algorithms"},{"key":"156_CR6357","doi-asserted-by":"crossref","unstructured":"Feder T, Mihail M (1992) Balanced matroids. In: Proceeding 24th ACM symposium on theory of computing, Victoria, 04\u201306 May, pp 26\u201338","DOI":"10.1145\/129712.129716"},{"key":"156_CR6358","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"GN Frederickson","year":"1985","unstructured":"Frederickson GN (1985) Data structures for on-line updating of minimum spanning trees. SIAM J Comput 14:781\u2013798","journal-title":"SIAM J Comput"},{"key":"156_CR6359","doi-asserted-by":"crossref","unstructured":"Frederickson GN (1991) Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. In: Proceeding 32nd symposium on foundations of computer science, San Juan, 01\u201304 Oct, pp 632\u2013641","DOI":"10.1109\/SFCS.1991.185429"},{"key":"156_CR6360","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1137\/0218008","volume":"18","author":"GN Frederickson","year":"1989","unstructured":"Frederickson GN, Srinivas MA (1989) Algorithms and data structures for an expanded family of matroid intersection problems. SIAM J Comput 18:112\u2013138","journal-title":"SIAM J Comput"},{"issue":"2","key":"156_CR6361","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/S0097539797327209","volume":"31","author":"MR Henzinger","year":"2001","unstructured":"Henzinger MR, King V (2001) Maintaining minimum spanning forests in dynamic graphs. SIAM J Comput 31(2):364\u2013374","journal-title":"SIAM J Comput"},{"issue":"4","key":"156_CR6362","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"MR Henzinger","year":"1999","unstructured":"Henzinger MR, King V (1999) Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J ACM 46(4):502\u2013516","journal-title":"J ACM"},{"key":"156_CR6363","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm J, de Lichtenberg K, Thorup M (2001) Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J ACM 48:723\u2013760","journal-title":"J ACM"},{"key":"#cr-split#-156_CR6364.1","unstructured":"Paul J, Simon W (1980) Decision trees and random access machines. In: Symposium \u00fcber Logik und Algorithmik"},{"key":"#cr-split#-156_CR6364.2","unstructured":"See also Mehlhorn K (1984) Sorting and searching. Springer, Berlin, pp 85-97"},{"key":"156_CR6365","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"RE Tarjan","year":"1985","unstructured":"Tarjan RE, Vishkin U (1985) An efficient parallel biconnectivity algorithm. SIAM J Comput 14:862\u2013874","journal-title":"SIAM J Comput"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:44:49Z","timestamp":1792107889000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_156","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}