{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:09:35Z","timestamp":1725458975640},"publisher-location":"Berlin\/Heidelberg","reference-count":19,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540188347"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0035827","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T15:40:10Z","timestamp":1138203610000},"page":"8-17","source":"Crossref","is-referenced-by-count":3,"title":["Getting back to the past in the union-find problem"],"prefix":"10.1007","author":[{"given":"Giorgio","family":"Gambosi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maurizio","family":"Talamo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","unstructured":"A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, 1974."},{"key":"2_CR2","first-page":"1259","volume":"3","author":"G.M. Adelson-Velskii","year":"1962","unstructured":"G.M. Adelson-Velskii, Y.M. Landis, \"An algorithm for the organization of the information\", Soviet. Math. Dokl. 3 (1962), 1259\u20131262.","journal-title":"Soviet. Math. Dokl."},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"N. Blum, \"On the single operation worst-case time complexity of the disjoint set union problem\", Proc. 2nd Symp. on Theoretical Aspects of Computer Science (1985), 32\u201338.","DOI":"10.1007\/BFb0023992"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"B. Bollobas, I. Simon, \"On the expecetd behavior of disjoint set union algorithms\", Proc. 17th ACM Symp. on Theory of Computing (1985), 224\u2013231.","DOI":"10.1145\/22145.22171"},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"R. Bayer, E. McCreight, \"Organization and maintenance of large ordered indices\", Acta Informatica 1 (1972), 173\u2013179.","journal-title":"Acta Informatica"},{"key":"2_CR6","unstructured":"G. Gambosi, G. F. Italiano, M. Talamo, \"Efficient introduction of heuristics in the Logic Programming environment\", in preparation."},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, R. E. Tarjan, \"A linear time algorithm for a special case of disjoint set union\", Proc. 15th ACM Symp. on Theory of Computing (1983), 246\u2013251.","DOI":"10.1145\/800061.808753"},{"key":"2_CR8","unstructured":"C. J. Hogger, Introduction to logic programming, Academic Press, 1984."},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0202024","volume":"2","author":"J. E. Hopcroft","year":"1973","unstructured":"J. E. Hopcroft, J. D. Ullman, \"Set merging algorithms\", SIAM J. Comput. 2 (1973), 294\u2013303.","journal-title":"SIAM J. Comput."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"H. Mannila, E. Ukkonen, \"The set union problem with backtracking\", Proc. 13th ICALP (1986), 236\u2013243.","DOI":"10.1007\/3-540-16761-7_73"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"H. Mannila, E. Ukkonen, \"On the complexity of unification sequences\", Proc. 3rd Int. Conf. on Logic Programming (1986), 122\u2013133.","DOI":"10.1007\/3-540-16492-8_69"},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J. Nievergelt","year":"1973","unstructured":"J. Nievergelt, E. M. Reingold, \"Binary search trees of bounded balance\", SIAM J. Comput. 2 (1973), 33\u201343.","journal-title":"SIAM J. Comput."},{"key":"2_CR13","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan, \"Efficiency of a good but not linear disjoint set union algorithm\", J. ACM 22 (1975), 215\u2013225.","journal-title":"J. ACM"},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R. E. Tarjan","year":"1979","unstructured":"R. E. Tarjan, \"A class of algorithms which require non linear time to maintain disjoint sets\", J. Computers and System Sciences 18 (1979), 110\u2013127.","journal-title":"J. Computers and System Sciences"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan, \"Amortized computational complexity\", SIAM J. Alg. Disc. Meth. 6 (1985), 306\u2013318.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"2_CR16","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R. E. Tarjan","year":"1984","unstructured":"R. E. Tarjan, J. van Leeuwen, \"Worst-case analysis of set union algorithms\", J. ACM 31 (1984), 245\u2013281.","journal-title":"J. ACM"},{"key":"2_CR17","unstructured":"Tarjan, Westbook: private communication"},{"key":"2_CR18","unstructured":"J. van Leeuwen, T. van der Weide, \"Alternative path compression techniques\", Techn.Rep. RUU-CS-77-3, Rijksuniversiteit Utrecht, The Netherlands."},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1145\/872734.806939","volume":"12","author":"D. H. D. Warren","year":"1977","unstructured":"D. H. D. Warren, L. M. Pereira, \"Prolog \u2014 the language and its implementation compared with LISP\", ACM SIGPLAN Notices 12 (1977), 109\u2013115.","journal-title":"ACM SIGPLAN Notices"}],"container-title":["Lecture Notes in Computer Science","STACS 88"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0035827.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:15:18Z","timestamp":1607552118000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0035827"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540188347"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0035827","relation":{},"subject":[]}}