{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T07:12:12Z","timestamp":1770534732134,"version":"3.49.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,8,25]],"date-time":"2014-08-25T00:00:00Z","timestamp":1408924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"name":"BSF","award":["2012338"],"award-info":[{"award-number":["2012338"]}]},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002808","name":"Carlsbergfondet","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002808","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":[[2014,10,28]]},"abstract":"<jats:p>\n            A union-find data structure maintains a collection of disjoint sets under the operations makeset, union, and find. Kaplan, Shafrir, and Tarjan [SODA 2002] designed data structures for an extension of the union-find problem in which items of the sets maintained may be deleted. The cost of a delete operation in their implementations is essentially the same as the cost of a find operation; namely,\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) worst-case and\n            <jats:italic>O<\/jats:italic>\n            (\u03b1\n            <jats:sub>\n              \u2308\n              <jats:italic>M<\/jats:italic>\n              \/\n              <jats:italic>N<\/jats:italic>\n              \u2309\n            <\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            )) amortized, where\n            <jats:italic>n<\/jats:italic>\n            is the number of items in the set returned by the find operation,\n            <jats:italic>N<\/jats:italic>\n            is the total number of makeset operations performed,\n            <jats:italic>M<\/jats:italic>\n            is the total number of find operations performed, and \u03b1\n            <jats:sub>\n              \u2308\n              <jats:italic>M<\/jats:italic>\n              \/\n              <jats:italic>N<\/jats:italic>\n              \u2309\n            <\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) is a functional inverse of Ackermann\u2019s function. They left open the question whether delete operations can be implemented more efficiently than find operations, for example, in\n            <jats:italic>o<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) worst-case time. We resolve this open problem by presenting a relatively simple modification of the classical union-find data structure that supports delete, as well as makeset and union operations, in\n            <jats:italic>constant<\/jats:italic>\n            worst-case time, while still supporting find operations in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) worst-case time and\n            <jats:italic>O<\/jats:italic>\n            (\u03b1\n            <jats:sub>\u2308 M\/N\u2309<\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            )) amortized time.\n          <\/jats:p>\n          <jats:p>\n            Our analysis supplies, in particular, a very concise potential-based amortized analysis of the standard union-find data structure that yields an\n            <jats:italic>O<\/jats:italic>\n            (\u03b1\n            <jats:sub>\n              \u2308\n              <jats:italic>M<\/jats:italic>\n              \/\n              <jats:italic>N<\/jats:italic>\n              \u2309\n            <\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            )) amortized bound on the cost of find operations. All previous potential-based analyses yielded the weaker amortized bound of\n            <jats:italic>O<\/jats:italic>\n            (\u03b1\n            <jats:sub>\n              \u2308\n              <jats:italic>M<\/jats:italic>\n              \/\n              <jats:italic>N<\/jats:italic>\n              \u2309\n            <\/jats:sub>\n            (\n            <jats:italic>N<\/jats:italic>\n            )). Furthermore, our tighter analysis extends to one-path variants of the path compression technique such as\n            <jats:italic>path splitting<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/2636922","type":"journal-article","created":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T13:03:31Z","timestamp":1409317411000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Union-Find with Constant Time Deletions"],"prefix":"10.1145","volume":"11","author":[{"given":"Stephen","family":"Alstrup","sequence":"first","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[{"name":"Technical University of Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theis","family":"Rauhe","sequence":"additional","affiliation":[{"name":"Octoshape Aps"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,25]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"A. V. Aho J. E. Hopcroft and J. D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading.   A. V. Aho J. E. Hopcroft and J. D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.005"},{"key":"e_1_2_1_3_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms (2nd ed.). MIT Press.   T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms (2nd ed.). MIT Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00015-4"},{"key":"e_1_2_1_5_1","volume-title":"Optimum branchings. Journal of Research of the National Bureau of Standards 71B","author":"Edmonds J.","year":"1967","unstructured":"J. Edmonds . 1967. Optimum branchings. Journal of Research of the National Bureau of Standards 71B ( 1967 ), 233--240. J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards 71B (1967), 233--240."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73040"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579168"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116878"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA\u201902)","author":"Kaplan H.","unstructured":"H. Kaplan , N. Shafrir , and R. E. Tarjan . 2002a. Union-find with deletions . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA\u201902) . 19--28. H. Kaplan, N. Shafrir, and R. E. Tarjan. 2002a. Union-find with deletions. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA\u201902). 19--28."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509990"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010305"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291179"},{"key":"e_1_2_1_13_1","volume-title":"The Design and Analysis of Algorithms","author":"Kozen D. L.","unstructured":"D. L. Kozen . 1992. The Design and Analysis of Algorithms . Springer , Berlin . D. L. Kozen. 1992. The Design and Analysis of Algorithms. Springer, Berlin."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_15_1","unstructured":"K. Mehlhorn and S. N\u00e4her. 1999. LEDA -- A Platform for Combinatorial and Geometric Computing. Cambridge University Press.   K. Mehlhorn and S. N\u00e4her. 1999. LEDA -- A Platform for Combinatorial and Geometric Computing. Cambridge University Press."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198517"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297027.1297061"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993711"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111583.1111585"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703439088"},{"key":"e_1_2_1_21_1","volume-title":"Newsletter of the ESPRIT II Basic Research Actions Program Project no. 3075 (ALCOM) 1","author":"Smid M.","year":"1990","unstructured":"M. Smid . 1990. A data structure for the union-find problem having good single-operation complexity. ALCOM: Algorithms Review , Newsletter of the ESPRIT II Basic Research Actions Program Project no. 3075 (ALCOM) 1 ( 1990 ), 1--12. M. Smid. 1990. A data structure for the union-find problem having good single-operation complexity. ALCOM: Algorithms Review, Newsletter of the ESPRIT II Basic Research Actions Program Project no. 3075 (ALCOM) 1 (1990), 1--12."},{"key":"e_1_2_1_22_1","unstructured":"Y. Takano. 2007. Implementing Uniqueness and Ownership Transfer in the Universe Type System. Master\u2019s thesis. ETH Zurich.  Y. Takano. 2007. Implementing Uniqueness and Ownership Transfer in the Universe Type System. Master\u2019s thesis. ETH Zurich."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804040"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203006"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070103"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan. 1983. Data Structures and Network Algorithms. SIAM.   R. E. Tarjan. 1983. Data Structures and Network Algorithms. SIAM.","DOI":"10.1137\/1.9781611970265"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636922","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2636922","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:22Z","timestamp":1750231162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,25]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2636922"],"URL":"https:\/\/doi.org\/10.1145\/2636922","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,25]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}