{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T05:27:36Z","timestamp":1737178056173,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540728443"},{"type":"electronic","value":"9783540728450"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-72845-0_7","type":"book-chapter","created":{"date-parts":[[2007,6,26]],"date-time":"2007-06-26T12:51:37Z","timestamp":1182862297000},"page":"80-93","source":"Crossref","is-referenced-by-count":9,"title":["Dynamic Trees in Practice"],"prefix":"10.1007","author":[{"given":"Robert E.","family":"Tarjan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","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: Proc. 15th SODA, pp. 524\u2013533, (2004)"},{"key":"7_CR2","unstructured":"Acar, U.A., Blelloch, G.E., Vittes, J.L.: An experimental analysis of change propagation in dynamic trees. In: Proc. 7th ALENEX, pp. 41\u201354 (2005)"},{"key":"7_CR3","volume-title":"Network Flows: Theory, algorithms, and applications","author":"R. Ahuja","year":"1993","unstructured":"Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, algorithms, and applications. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/3-540-63165-8_184","volume-title":"Automata, Languages and Programming","author":"S. Alstrup","year":"1997","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Minimizing diameters of dynamic trees. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 270\u2013280. Springer, Heidelberg (1997)"},{"key":"7_CR5","unstructured":"Alstrup, S., Holm, J., Thorup, M.: On the power and speed of top trees. Unpublished manuscript (1999)"},{"issue":"2","key":"7_CR6","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 TALG\u00a01(2), 243\u2013264 (2005)","journal-title":"ACM TALG"},{"key":"7_CR7","unstructured":"Anderson, R.: The washington graph generator. In: Johnson, D.S., McGeoch, C.C.: (eds.), DIMACS Series in Discrete Mathematics and Computer Science, pp. 580\u2013581. AMS (1993)"},{"key":"7_CR8","first-page":"87","volume":"16","author":"R. Bellman","year":"1958","unstructured":"Bellman, R.: On a routing problem. Quarterly Mathematics\u00a016, 87\u201390 (1958)","journal-title":"Quarterly Mathematics"},{"key":"7_CR9","series-title":"Lecture Notes in Artificial Intelligence","first-page":"111","volume-title":"Machine Learning and Its Applications","author":"G. Cattaneo","year":"2002","unstructured":"Cattaneo, G., Faruolo, P., Ferraro-Petrillo, U., Italiano, G.F.: Maintaining dynamic minimum spanning trees: An experimental study. In: Paliouras, G., Karkaletsis, V., Spyropoulos, C.D. (eds.) Machine Learning and Its Applications. LNCS (LNAI), vol.\u00a02049, pp. 111\u2013125. Springer, Heidelberg (2002)"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. JACM\u00a019, 248\u2013264 (1972)","journal-title":"JACM"},{"issue":"4","key":"7_CR11","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. Comp.\u00a014(4), 781\u2013798 (1985)","journal-title":"SIAM J. Comp."},{"issue":"2","key":"7_CR12","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. Comp.\u00a026(2), 484\u2013538 (1997)","journal-title":"SIAM J. Comp."},{"issue":"1","key":"7_CR13","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 data structure for dynamically maintaining rooted trees. J. Alg.\u00a024(1), 37\u201365 (1997)","journal-title":"J. Alg."},{"key":"7_CR14","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 network simplex algorithm for the maximum flow problem. Mathematical Programming\u00a050, 277\u2013290 (1991)","journal-title":"Mathematical Programming"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarihmic time per operation. In: Proc. 29th STOC, pp. 519\u2013527 (1997)","DOI":"10.1145\/225058.225269"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Molad, E., Tarjan, R.E.: Dynamic rectangular intersection with priorities. In: Proc. 35th STOC, pp. 639\u2013648 (2003)","DOI":"10.1145\/780632.780635"},{"key":"7_CR17","unstructured":"Klein, P.N.: Multiple-source shortest paths in planar graphs. In: Proc. 16th SODA, pp. 146\u2013155 (2005)"},{"key":"7_CR18","unstructured":"Langerman, S.: On the shooter location problem: Maintaining dynamic circular-arc graphs. In: Proc. 12th CCCG, pp. 29\u201335 (2000)"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Reif, J.H.: Parallel tree contraction and its applications. In: Proc. 26th FOCS, pp. 478\u2013489 (1985)","DOI":"10.1109\/SFCS.1985.43"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Radzik, T.: Implementation of dynamic trees with in-subtree operations. ACM JEA, 3(9) (1998)","DOI":"10.1145\/297096.297144"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Ribeiro, C.C., Toso, R.F.: Experimental analysis of algorithms for updating minimum spanning trees on graphs subject to changes on edge weights. In: Proc. 6th WEA, pp. 393\u2013405, (2007)","DOI":"10.1007\/978-3-540-72845-0_30"},{"issue":"3","key":"7_CR22","first-page":"362","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. JCSS\u00a026(3), 362\u2013391 (1983)","journal-title":"JCSS"},{"issue":"3","key":"7_CR23","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. JACM\u00a032(3), 652\u2013686 (1985)","journal-title":"JACM"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. SIAM Press (1983)","DOI":"10.1137\/1.9781611970265"},{"key":"7_CR25","first-page":"169","volume":"78","author":"R.E. Tarjan","year":"1997","unstructured":"Tarjan, R.E.: Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Mathematical Programming\u00a078, 169\u2013177 (1997)","journal-title":"Mathematical Programming"},{"key":"7_CR26","unstructured":"Tarjan, R.E., Werneck, R.F.: Self-adjusting top trees. In: Proc. 16th SODA, pp. 813\u2013822 (2005)"},{"key":"7_CR27","unstructured":"Werneck, R.F.: Design and Analysis of Data Structures for Dynamic Trees. PhD thesis, Princeton University (2006)"},{"key":"7_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/3-540-36383-1_11","volume-title":"Experimental Algorithms: From Algorithm Design to Robust and Efficient Software","author":"C.D. Zaroliagis","year":"2002","unstructured":"Zaroliagis, C.D.: Implementations and experimental studies of dynamic graph algorithms. In: Fleischer, R., Moret, B., Schmidt, E.M. (eds.) Experimental Algorithms: From Algorithm Design to Robust and Efficient Software. LNCS, pp. 229\u2013278. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72845-0_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T22:14:20Z","timestamp":1737152060000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72845-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540728443","9783540728450"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72845-0_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}