{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T05:17:43Z","timestamp":1672550263159},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[1998,9]]},"abstract":"We describe an implementation of dynamic trees with \"in-subtree\" operations. Our implementation follows Sleator and Tarjan's framework of dynamic-tree implementations based on splay trees. We consider the following two examples of \"in-subtree\" operations. (a) For a given node v, find a node with the minimum key in the subtree rooted at v. (b) For a given node v, find a random node with key X in the subtree rooted at v (value X is fixed throughout the whole computation). The first operation may provide support for edge deletions in the dynamic minimum spanning tree problem. The second one may be useful in local search methods for degree-constrained minimum spanning tree problems. We conducted experiments with our dynamic-tree implementation within these two contexts, and the results suggest that this implementation may lead to considerably faster codes than straightforward approaches do.<\/jats:p>","DOI":"10.1145\/297096.297144","type":"journal-article","created":{"date-parts":[[2005,8,2]],"date-time":"2005-08-02T06:34:09Z","timestamp":1122964449000},"page":"9","source":"Crossref","is-referenced-by-count":6,"title":["Implementation of dynamic trees with in-subtree operations"],"prefix":"10.1145","volume":"3","author":[{"given":"Tomasz","family":"Radzik","sequence":"first","affiliation":[{"name":"King's College, London"}]}],"member":"320","published-online":{"date-parts":[[1998,9]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218065"},{"key":"e_1_2_2_2_1","volume-title":"Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"AMATO G.","year":"1997","unstructured":"AMATO , G. , CATTANEO , G. , AND ITALIANO , G. F. 1997 . Experimental analysis of dynamic minimum spanning tree algorithms . In Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms (1997). AMATO, G., CATTANEO, G., AND ITALIANO, G. F. 1997. Experimental analysis of dynamic minimum spanning tree algorithms. In Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms (1997)."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00940812"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267818"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1018"},{"key":"e_1_2_2_8_1","first-page":"101","volume-title":"B. KORTE, L. LOV\u00c1S, H. PR\u00d6MEL, AND A","author":"GOLDBERG A. V.","unstructured":"GOLDBERG , A. V. , TARDOS , E. , AND TARJAN , R. E. 1990. Network Flow Algorithms . In B. KORTE, L. LOV\u00c1S, H. PR\u00d6MEL, AND A . SCHRIJVER Eds., Paths, Flows , and VLSI-layout, pp. 101 - 164 . Springer-Verlag . GOLDBERG, A. V., TARDOS, E., AND TARJAN, R. E. 1990. Network Flow Algorithms. In B. KORTE, L. LOV\u00c1S, H. PR\u00d6MEL, AND A. SCHRIJVER Eds., Paths, Flows, and VLSI-layout, pp. 101-164. Springer-Verlag."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76368"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.15.3.430"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646251.685829"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/204865.204889"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_2_16_1","volume-title":"Data Structures and Network Algorithms","author":"TARJAN R. E.","unstructured":"TARJAN , R. E. 1983. Data Structures and Network Algorithms . Society for Industrial and Applied Mathematics , Philadelphia, PA . TARJAN, R. E. 1983. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/297096.297144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T10:42:18Z","timestamp":1672483338000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/297096.297144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,9]]},"references-count":16,"alternative-id":["10.1145\/297096.297144"],"URL":"http:\/\/dx.doi.org\/10.1145\/297096.297144","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[1998,9]]}}}