{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T20:01:10Z","timestamp":1742932870157,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":18,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_121","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:36:18Z","timestamp":1214505378000},"page":"260-264","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Trees"],"prefix":"10.1007","author":[{"given":"Renato F.","family":"Werneck","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"121_CR1_121","unstructured":"Acar, U.A., Blelloch, G.E., Harper, R., Vittes, J.L., Woo, S.L.M.: Dynamizing static algorithms, with applications to dynamic trees and history independence. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0524\u2013533. SIAM (2004)"},{"key":"121_CR2_121","unstructured":"Acar, U.A., Blelloch, G.E., Vittes, J.L.: An experimental analysis of change propagation in dynamic trees. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX), pp.\u00a041\u201354 (2005)"},{"key":"121_CR3_121","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Minimizing diameters of dynamic trees. In: Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP), Bologna, Italy, 7\u201311 July 1997. Lecture Notes in Computer Science, vol.\u00a01256, pp.\u00a0270\u2013280. Springer (1997)","DOI":"10.1007\/3-540-63165-8_184"},{"issue":"2","key":"121_CR4_121","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.: Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms 1(2), 243\u2013264 (2005)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"121_CR5_121","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"S.W. Bent","year":"1985","unstructured":"Bent, S.W., Sleator, D.D., Tarjan, R.E.: Biased search trees. SIAM J.\u00a0Comput. 14(3), 545\u2013568 (1985)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"121_CR6_121","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"Frederickson, G.N.: Data structures for on-line update of minimum spanning trees, with applications. SIAM J.\u00a0Comput. 14(4), 781\u2013798 (1985)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"121_CR7_121","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1137\/S0097539792226825","volume":"26","author":"G.N. Frederickson","year":"1997","unstructured":"Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J.\u00a0Comput. 26(2), 484\u2013538 (1997)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"121_CR8_121","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jagm.1996.0835","volume":"24","author":"G.N. Frederickson","year":"1997","unstructured":"Frederickson, G.N.: A\u00a0data structure for dynamically maintaining rooted trees. J.\u00a0Algorithms 24(1), 37\u201365 (1997)","journal-title":"J. Algorithms"},{"key":"121_CR9_121","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01594940","volume":"50","author":"A.V. Goldberg","year":"1991","unstructured":"Goldberg, A.V., Grigoriadis, M.D., Tarjan, R.E.: Use of dynamic trees in a\u00a0network simplex algorithm for the maximum flow problem. Math. Progr. 50, 277\u2013290 (1991)","journal-title":"Math. Progr."},{"key":"121_CR10_121","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarihmic time per operation. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pp.\u00a0519\u2013527 (1997)","DOI":"10.1145\/225058.225269"},{"key":"121_CR11_121","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Reif, J.H.: Parallel tree contraction and its applications. In: Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.\u00a0478\u2013489 (1985)","DOI":"10.1109\/SFCS.1985.43"},{"key":"121_CR12_121","doi-asserted-by":"crossref","unstructured":"P\u02d8atra\u015fcu, M., Demaine, E.D.: Lower bounds for dynamic connectivity. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp.\u00a0546\u2013553 (2004)","DOI":"10.1145\/1007352.1007435"},{"issue":"3","key":"121_CR13_121","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A\u00a0data structure for dynamic trees. J.\u00a0Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"121_CR14_121","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J.\u00a0ACM 32(3), 652\u2013686 (1985)","journal-title":"J. ACM"},{"key":"121_CR15_121","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E.: Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Prog. 78, 169\u2013177 (1997)","DOI":"10.1007\/BF02614369"},{"key":"121_CR16_121","unstructured":"Tarjan, R.E., Werneck, R.F.: Self-adjusting top trees. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0813\u2013822 (2005)"},{"key":"121_CR17_121","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E., Werneck, R.F.: Dynamic trees in practice. In: Proceedings of the 6th Workshop on Experimental Algorithms (WEA). Lecture Notes in Computer Science, vol.\u00a04525, pp.\u00a080\u201393 (2007)","DOI":"10.1007\/978-3-540-72845-0_7"},{"key":"121_CR18_121","unstructured":"Werneck, R.F.: Design and Analysis of Data Structures for Dynamic Trees. Ph.\u202fD. thesis, Princeton University (2006)"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T21:32:40Z","timestamp":1738272760000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_121"}},"subtitle":["2005; Tarjan, Werneck"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_121","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}