{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:25Z","timestamp":1750308805650,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["975\/06"],"award-info":[{"award-number":["975\/06"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["112-0188-1234-12CCF-0830676CCF-0832797"],"award-info":[{"award-number":["112-0188-1234-12CCF-0830676CCF-0832797"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2006204"],"award-info":[{"award-number":["2006204"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>\n            Motivated by an application in computational geometry, we consider a novel variant of the problem of efficiently maintaining a forest of dynamic rooted trees. This variant includes an operation that merges two tree paths. In contrast to the standard problem, in which a single operation can only add or delete one arc, one merge can add and delete up to a linear number of arcs. In spite of this, we develop three different methods that need only polylogarithmic time per operation. The first method extends a solution of Farach and Thorup [1998] for the special case of paths. Each merge takes\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) amortized time on an\n            <jats:italic>n<\/jats:italic>\n            -node forest and each standard dynamic tree operation takes\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) time; the latter bound is amortized, worst case, or randomized depending on the underlying data structure. For the special case that occurs in the motivating application, in which arbitrary arc deletions (cuts) do not occur, we give a method that takes\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) time per operation, including merging. This is best possible in a model of computation with an \u03a9(\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) lower bound for sorting\n            <jats:italic>n<\/jats:italic>\n            numbers, since such sorting can be done in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) tree operations. For the even-more-special case in which there are no cuts and no\n            <jats:italic>parent<\/jats:italic>\n            queries, we give a method that uses standard dynamic trees as a black box: each mergeable tree operation becomes a constant number of standard dynamic tree operations. This third method can also be used in the motivating application, but only by changing the algorithm in the application. Each of our three methods needs different analytical tools and reveals different properties of dynamic trees.\n          <\/jats:p>","DOI":"10.1145\/1921659.1921660","type":"journal-article","created":{"date-parts":[[2011,3,29]],"date-time":"2011-03-29T12:01:30Z","timestamp":1301400090000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Data structures for mergeable trees"],"prefix":"10.1145","volume":"7","author":[{"given":"Loukas","family":"Georgiadis","sequence":"first","affiliation":[{"name":"University of Western Macedonia, Kozani, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nira","family":"Shafrir","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ and Hewlett-Packard Laboratories, Palo Alto, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[{"name":"Microsoft Research, La Avenida, Moutain View, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,3,31]]},"reference":[{"volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 524--533","author":"Acar U. A.","key":"e_1_2_1_1_1","unstructured":"Acar , U. A. , Blelloch , G. E. , Harper , R. , Vittes , J. L. , and Woo , S. L. M. 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, 524--533 . Acar, U. A., Blelloch, G. E., Harper, R., Vittes, J. L., and Woo, S. L. M. 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, 524--533."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997871"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1265-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103966"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322127"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979732699X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797326988"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009202"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0835"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109602"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594940"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_47"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509990"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_19_1","article-title":"A data structure for the union-find problem having good single-operation complexity","author":"Smid M.","year":"1990","unstructured":"Smid , M. 1990 . A data structure for the union-find problem having good single-operation complexity . Algor. Rev. Newlett. ESPRITT II Basic Res. Actions Program Project no. 3072 (ALCOM) 1. Smid, M. 1990. A data structure for the union-find problem having good single-operation complexity. Algor. Rev. Newlett. ESPRITT II Basic Res. Actions Program Project no. 3072 (ALCOM) 1.","journal-title":"Algor. Rev. Newlett. ESPRITT II Basic Res. Actions Program Project no. 3072 (ALCOM) 1."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 813--822","author":"Tarjan R. E.","key":"e_1_2_1_21_1","unstructured":"Tarjan , R. E. and Werneck , R. F . 2005. Self-Adjusting top trees . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 813--822 . Tarjan, R. E. and Werneck, R. F. 2005. Self-Adjusting top trees. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 813--822."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217010"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921659.1921660","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1921659.1921660","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:08Z","timestamp":1750278368000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921659.1921660"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1921659.1921660"],"URL":"https:\/\/doi.org\/10.1145\/1921659.1921660","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2008-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}