{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:28Z","timestamp":1750307728919,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["112-0188-1234-12"],"award-info":[{"award-number":["112-0188-1234-12"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>Dynamic tree data structures maintain forests that change over time through edge insertions and deletions. Besides maintaining connectivity information in logarithmic time, they can support aggregation of information over paths, trees, or both. We perform an experimental comparison of several versions of dynamic trees: ST-trees, ET-trees, RC-trees, and two variants of top trees (self-adjusting and worst-case). We quantify their strengths and weaknesses through tests with various workloads, most stemming from practical applications. We observe that a simple, linear-time implementation is remarkably fast for graphs of small diameter, and that worst-case and randomized data structures are best when queries are very frequent. The best overall performance, however, is achieved by self-adjusting ST-trees.<\/jats:p>","DOI":"10.1145\/1498698.1594231","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":9,"title":["Dynamic trees in practice"],"prefix":"10.1145","volume":"14","author":[{"given":"Robert E.","family":"Tarjan","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ, USA and HP Labs, Palo Alto, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[{"name":"Microsoft Research Silicon Valley, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04)","author":"Acar U. A.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05)","author":"Acar U. A.","key":"e_1_2_1_2_1"},{"volume-title":"Proceedings of the 4th Colloquium on Mathematics and Computer Science. Discrete Mathematics and Theoretical Computer Science","author":"Addario-Berry L.","key":"e_1_2_1_3_1"},{"volume-title":"Network Flows: Theory, Algorithms, and Applications","year":"1993","author":"Ahuja R.","key":"e_1_2_1_4_1"},{"volume-title":"Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97)","author":"Alstrup S.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","unstructured":"Alstrup S. Holm J. and Thorup M. 1999. On the power and speed of top trees. Unpublished manuscript.  Alstrup S. Holm J. and Thorup M. 1999. On the power and speed of top trees. Unpublished manuscript."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103966"},{"key":"e_1_2_1_8_1","unstructured":"Anderson R. 1993. The Washington graph generator. In DIMACS Series in Discrete Mathematics and Computer Science D. S. Johnson and C. C. McGeoch Eds. AMS 580--581.  Anderson R. 1993. The Washington graph generator. In DIMACS Series in Discrete Mathematics and Computer Science D. S. Johnson and C. C. McGeoch Eds. AMS 580--581."},{"key":"e_1_2_1_9_1","first-page":"87","article-title":"On a routing problem","volume":"16","author":"Bellman R.","year":"1958","journal-title":"Q. Math."},{"volume-title":"Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02)","author":"Cattaneo G.","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'08)","author":"Cherkassky B. V.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050058"},{"key":"e_1_2_1_13_1","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"Dinic E. A.","year":"1970","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_15_1","unstructured":"Ford Jr. L. 1956. Network flow theory. Tech. rep. P-932 The Rand Corporation.  Ford Jr. L. 1956. Network flow theory. Tech. rep. P-932 The Rand Corporation."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226825"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0835"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594940"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225269"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780635"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05)","year":"2005","author":"Klein P. N.","key":"e_1_2_1_22_1"},{"volume-title":"Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG'00)","year":"2000","author":"Langerman S.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.43"},{"volume-title":"Proceedings of the International Symposium on the Theory of Switching","year":"1959","author":"Moore E. F.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297144"},{"volume-title":"Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07)","author":"Ribeiro C. C.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Tarjan R. E. 1983. Data Structures and Network Algorithms. SIAM Philadelphia.   Tarjan R. E. 1983. Data Structures and Network Algorithms. SIAM Philadelphia.","DOI":"10.1137\/1.9781611970265"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614369"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05)","author":"Tarjan R. E.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","unstructured":"Werneck R. F. 2006. Design and analysis of data structures for dynamic trees. Ph.D. thesis Princeton University.   Werneck R. F. 2006. Design and analysis of data structures for dynamic trees. Ph.D. thesis Princeton University."},{"volume-title":"Experimental Algorithms: From Algorithm Design to Robust and Efficient Software","author":"Zaroliagis C. D.","key":"e_1_2_1_34_1"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1594231","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498698.1594231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:38Z","timestamp":1750253918000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1594231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":34,"alternative-id":["10.1145\/1498698.1594231"],"URL":"https:\/\/doi.org\/10.1145\/1498698.1594231","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}