{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T17:04:24Z","timestamp":1743008664460,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":18,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","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_121","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:12Z","timestamp":1461268992000},"page":"605-609","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dynamic Trees"],"prefix":"10.1007","author":[{"given":"Renato F.","family":"Werneck","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"98_CR4432","unstructured":"Acar UA, Blelloch GE, Harper R, Vittes JL, Woo SLM (2004) Dynamizing static algorithms, with applications to dynamic trees and history independence. In: Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM, pp 524\u2013533"},{"key":"98_CR4433","unstructured":"Acar UA, Blelloch GE, Vittes JL (2005) An experimental analysis of change propagation in dynamic trees. In: Proceedings of the 7th workshop on algorithm engineering and experiments (ALENEX). pp 41\u201354"},{"key":"98_CR4434","doi-asserted-by":"crossref","unstructured":"Alstrup S, Holm J, de Lichtenberg K, Thorup M (1997) Minimizing diameters of dynamic trees. In: Proceedings of the 24th international colloquium on automata, languages and programming (ICALP), Bologna, 7\u201311 July 1997. Lecture notes in computer science, vol 1256. Springer, pp 270\u2013280","DOI":"10.1007\/3-540-63165-8_184"},{"issue":"2","key":"98_CR4435","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1145\/1103963.1103966","volume":"1","author":"S Alstrup","year":"2005","unstructured":"Alstrup S, Holm J, Thorup M, de Lichtenberg K (2005) Maintaining information in fully dynamic trees with top trees. ACM Trans Algorithm 1(2):243\u2013264","journal-title":"ACM Trans Algorithms"},{"issue":"3","key":"98_CR4436","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"SW Bent","year":"1985","unstructured":"Bent SW, Sleator DD, Tarjan RE (1985) Biased search trees. SIAM J Comput 14(3):545\u2013568","journal-title":"SIAM J Comput"},{"issue":"4","key":"98_CR4437","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 update of minimum spanning trees, with applications. SIAM J Comput 14(4):781\u2013798","journal-title":"SIAM J Comput"},{"issue":"2","key":"98_CR4438","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1137\/S0097539792226825","volume":"26","author":"GN Frederickson","year":"1997","unstructured":"Frederickson GN (1997) Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J Comput 26(2):484\u2013538","journal-title":"SIAM J Comput"},{"issue":"1","key":"98_CR4439","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jagm.1996.0835","volume":"24","author":"GN Frederickson","year":"1997","unstructured":"Frederickson GN (1997) A data structure for dynamically maintaining rooted trees. J Algorithms 24(1):37\u201365","journal-title":"J Algorithms"},{"key":"98_CR4440","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01594940","volume":"50","author":"AV Goldberg","year":"1991","unstructured":"Goldberg AV, Grigoriadis MD, Tarjan RE (1991) Use of dynamic trees in a network simplex algorithm for the maximum flow problem. Math Program 50:277\u2013290","journal-title":"Math Program"},{"key":"98_CR4441","unstructured":"Henzinger MR, King V (1997) Randomized fully dynamic graph algorithms with polylogarihmic time per operation. In: Proceedings of the 27th annual ACM symposium on theory of computing (STOC), pp 519\u2013527"},{"key":"98_CR4442","doi-asserted-by":"crossref","unstructured":"Miller GL, Reif JH (1985) Parallel tree contraction and its applications. In: Proceedings of the 26th annual IEEE symposium on foundations of computer science (FOCS), pp 478\u2013489","DOI":"10.1109\/SFCS.1985.43"},{"key":"98_CR4443","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu M, Demaine ED (2004) Lower bounds for dynamic connectivity. In: Proceedings of the 36th annual ACM symposium on theory of computing (STOC), pp 546\u2013553","DOI":"10.1145\/1007352.1007435"},{"issue":"3","key":"98_CR4444","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator DD, Tarjan RE (1983) A data structure for dynamic trees. J Comput Syst Sci 26(3):362\u2013391","journal-title":"J Comput Syst Sci"},{"issue":"3","key":"98_CR4445","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator DD, Tarjan RE (1985) Self-adjusting binary search trees. J ACM 32(3):652\u2013686","journal-title":"J ACM"},{"key":"98_CR4446","first-page":"169","volume":"78","author":"RE Tarjan","year":"1997","unstructured":"Tarjan RE (1997) Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math Program 78:169\u2013177","journal-title":"Math Program"},{"key":"98_CR4447","unstructured":"Tarjan RE, Werneck RF (2005) Self-adjusting top trees. In: Proceedings of the 16th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 813\u2013822"},{"key":"98_CR4448","doi-asserted-by":"crossref","unstructured":"Tarjan RE, Werneck RF (2007) Dynamic trees in practice. In: Proceedings of the 6th workshop on experimental algorithms (WEA). Lecture notes in computer science, vol 4525, pp 80\u201393","DOI":"10.1007\/978-3-540-72845-0_7"},{"key":"98_CR4449","unstructured":"Werneck RF (2006) Design and analysis of data structures for dynamic trees. PhD thesis, Princeton University"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T16:09:58Z","timestamp":1553098198000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_121","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"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}