{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:42:39Z","timestamp":1787499759014,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540631651","type":"print"},{"value":"9783540691945","type":"electronic"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"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":[[1997]]},"DOI":"10.1007\/3-540-63165-8_214","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:11:33Z","timestamp":1330279893000},"page":"594-604","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":35,"title":["Maintaining minimum spanning trees in dynamic graphs"],"prefix":"10.1007","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":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"56_CR1","unstructured":"T. Corman, C. Leiserson, and Rivest. Introduction to Algorithms. MIT Press (1989), p. 381\u2013399."},{"key":"56_CR2","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02574030","volume":"13","author":"D. Eppstein","year":"1995","unstructured":"D. Eppstein, \u201cDynamic Euclidean minimum spanning trees and extrema of binary functions\u201d, Disc. Comp. Geom. 13 (1995), 111\u2013122.","journal-title":"Disc. Comp. Geom."},{"key":"56_CR3","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano, \u201cImproved Sparsification\u201d, Tech. Report 93-20, Department of Information and Computer Science, University of California, Irvine, CA 92717."},{"key":"56_CR4","doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano, A. Nissenzweig, \u201cSparsification \u2014 A Technique for Speeding up Dynamic Graph Algorithms\u201d Proc. 33rd Symp. on Foundations of Computer Science, 1992, 60\u201369.","DOI":"10.1109\/SFCS.1992.267818"},{"key":"56_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/322234.322235","volume":"28","author":"S. Even","year":"1981","unstructured":"S. Even and Y. Shiloach, \u201cAn On-Line Edge-Deletion Problem\u201d, J. ACM 28 (1981), 1\u20134.","journal-title":"J. ACM"},{"key":"56_CR6","doi-asserted-by":"crossref","unstructured":"T. Feder and M. Mihail, \u201cBalanced matroids\u201d, Proc. 24th A Cm Symp. on Theory of Computing, 1992, 26\u201338.","DOI":"10.1145\/129712.129716"},{"key":"56_CR7","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. N. Frederickson","year":"1985","unstructured":"G. N. Frederickson, \u201cData Structures for On-line Updating of Minimum Spanning Trees\u201d, SIAM J. Comput., 14 (1985), 781\u2013798.","journal-title":"SIAM J. Comput."},{"key":"56_CR8","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1137\/0218008","volume":"18","author":"G. N. Frederickson","year":"1989","unstructured":"G. N. Frederickson and M. A. Srinivas, \u201cAlgorithms and data structures for an expanded family of matroid intersection problems\u201d, SIAM J. Corn-put. 18 (1989), 112\u2013138.","journal-title":"SIAM J. Corn-put"},{"key":"56_CR9","doi-asserted-by":"crossref","unstructured":"M. R. Henzinger and V. King. Randomized Dynamic Graph Algorithms with Polylogarithmic Time per Operation. Proc. 27th ACM Symp. on Theory of Computing, 1995, 519\u2013527.","DOI":"10.1145\/225058.225269"},{"key":"56_CR10","doi-asserted-by":"crossref","unstructured":"M. R. Henzinger and M. Thorup. Improved Sampling with Applications to Dynamic Graph Algorithms. To appear in Proc. 23rd International Colloquium on Automata, Languages, and Programming (ICALP), LNCS 1099, Springer-Verlag, 1996.","DOI":"10.1007\/3-540-61440-0_136"},{"key":"56_CR11","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. \u201cData Structures and Algorithms 1: Sorting and Searching\u201d, Springer-Verlag, 1984.","DOI":"10.1007\/978-3-642-69672-5"},{"key":"56_CR12","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"H. Nagamochi and T. Ibaraki, \u201cLinear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph\u201d, Algorithmica 7, 1992, 583\u2013596.","journal-title":"Algorithmica"},{"key":"56_CR13","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"24","author":"D. D. Sleator","year":"1983","unstructured":"D. D. Sleator, R. E. Tarjan, \u201cA data structure for dynamic trees\u201d J. Comput. System Sci. 24, 1983, 362\u2013381.","journal-title":"J. Comput. System Sci"},{"key":"56_CR14","unstructured":"R. E. Tarjan, Data Structures and Network Flow, SIAM (1983) p. 71."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63165-8_214","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T08:47:34Z","timestamp":1558255654000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63165-8_214"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540631651","9783540691945"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-63165-8_214","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"8 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}