{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:46:24Z","timestamp":1767339984493},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540275800"},{"type":"electronic","value":"9783540316916"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11523468_7","type":"book-chapter","created":{"date-parts":[[2010,7,18]],"date-time":"2010-07-18T14:58:59Z","timestamp":1279465139000},"page":"78-89","source":"Crossref","is-referenced-by-count":5,"title":["Union-Find with Constant Time Deletions"],"prefix":"10.1007","author":[{"given":"Stephen","family":"Alstrup","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge","family":"Li G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theis","family":"Rauhe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Ben-Amram, A.M., Rauhe, T.: Worst-case and amortised optimality in union-find. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC 1999), May 1999, pp. 499\u2013506 (1999)","DOI":"10.1145\/301250.301383"},{"issue":"1","key":"7_CR3","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/s004530010077","volume":"30","author":"A.M. Ben-Amram","year":"2001","unstructured":"Ben-Amram, A.M., Galil, Z.: A generalization of a lower bound technique due to Fredman and Saks. Algorithmica\u00a030(1), 34\u201366 (2001)","journal-title":"Algorithmica"},{"issue":"4","key":"7_CR4","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.1137\/0215072","volume":"15","author":"N. Blum","year":"1986","unstructured":"Blum, N.: On the single-operation worst-case time complexity of the disjoint set union problem. SIAM J. Comput.\u00a015(4), 1021\u20131024 (1986)","journal-title":"SIAM J. Comput."},{"key":"7_CR5","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/73007.73040","volume-title":"Proceedings of the 21st Annual Symposium on Theory of Computing (STOC 1989)","author":"M. Fredman","year":"1989","unstructured":"Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. In: Proceedings of the 21st Annual Symposium on Theory of Computing (STOC 1989), May 1989, pp. 345\u2013354. ACM Association for Computing Machinery, New York (1989)"},{"issue":"3","key":"7_CR7","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1145\/116873.116878","volume":"23","author":"Z. Galil","year":"1991","unstructured":"Galil, Z., Italiano, G.F.: Data structures and algorithms for disjoint set union problems. ACM Computing Surveys\u00a023(3), 319 (1991)","journal-title":"ACM Computing Surveys"},{"key":"7_CR8","unstructured":"Kaplan, H., Shafrir, N., Tarjan, R.E.: Union-find with deletions. In: Proc. of the 13th ACM-SIAM Symp. on Discrete Mathematics (SODA), pp. 19\u201328"},{"key":"7_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4400-4","volume-title":"The Design and Analysis of Algorithms","author":"D.L. Kozen","year":"1992","unstructured":"Kozen, D.L.: The Design and Analysis of Algorithms. Springer, Berlin (1992)"},{"issue":"3","key":"7_CR10","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1137\/S0097539703439088","volume":"34","author":"R. Seidel","year":"2005","unstructured":"Seidel, R., Sharir, M.: Top-down analysis of path compression. SIAM J. Comput.\u00a034(3), 515\u2013525 (2005)","journal-title":"SIAM J. Comput."},{"key":"7_CR11","unstructured":"Smid, M.: 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)"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear disjoint set union algorithm. Journal of the ACM\u00a022, 215\u2013225 (1975)","journal-title":"Journal of the ACM"},{"issue":"2","key":"7_CR13","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., van Leeuwen, J.: Worst-case analysis of set union algorithms. Journal of the ACM\u00a031(2), 245\u2013281 (1984)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11523468_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T02:46:02Z","timestamp":1559270762000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11523468_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540275800","9783540316916"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11523468_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}