{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:20:56Z","timestamp":1725456056183},"publisher-location":"Berlin\/Heidelberg","reference-count":19,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540543430"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028283","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T05:52:14Z","timestamp":1132638734000},"page":"449-460","source":"Crossref","is-referenced-by-count":1,"title":["Fully persistent data structures for disjoint set union problems"],"prefix":"10.1007","author":[{"given":"Giuseppe F.","family":"Italiano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neil","family":"Sarnak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"40_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"40_CR2","unstructured":"A. Apostolico, G. Gambosi, G. F. Italiano, M. Talamo, \u201cThe set union problem with unlimited backtracking\u201d, Tech. Rep. CS-TR-908, Department of Computer Science, Purdue University, 1989."},{"key":"40_CR3","unstructured":"D. Bacon, V. Nguyen, R. Strom, D. Yellin, \u201cThe Hermes language reference manual\u201d, IBM Tech. Rep., 1990."},{"key":"40_CR4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0020-0190(80)90001-0","volume":"11","author":"L. Banachowski","year":"1980","unstructured":"L. Banachowski, \u201cA complement to Tarjan's result about the lower bound on the complexity of the set union problem\u201d, Inform. Processing Lett. 11 (1980), 59\u201365.","journal-title":"Inform. Processing Lett."},{"key":"40_CR5","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1137\/0215072","volume":"15","author":"N. Blum","year":"1986","unstructured":"N. Blum, \u201cOn the single operation worst-case time complexity of the disjoint set union problem\u201d, SIAM J. Comput. 15 (1986), 1021\u20131024.","journal-title":"SIAM J. Comput."},{"key":"40_CR6","unstructured":"R. B. K. Dewar, E. Schonberg, J. T. Schwartz, \u201cIntroduction to the use of the Set-Theoretic Programming Language SETL\u201d, Courant Institute of Mathematical Sciences, Computer Science Department, New York University, 1981."},{"key":"40_CR7","first-page":"67","volume-title":"Proc. Workshop on Algorithms and Data Structures (WADS 1989), Lecture Notes in Computer Science vol. 382","author":"P. Dietz","year":"1989","unstructured":"P. Dietz, \u201cFully persistent arrays\u201d, Proc. Workshop on Algorithms and Data Structures (WADS 1989), Lecture Notes in Computer Science vol. 382, Springer-Verlag, Berlin, 1989, 67\u201374."},{"key":"40_CR8","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J. R. Driscoll","year":"1989","unstructured":"J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan, \u201cMaking data structures persistent\u201d, J. Comput. Sys. Sci. 38 (1989), 86\u2013124.","journal-title":"J. Comput. Sys. Sci."},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"M. L. Fredman, M. E. Saks, \u201cThe cell probe complexity of dynamic data structures\u201d, Proc. 21th Annual ACM Symp. on Theory of Computing, 1989, 345\u2013354.","DOI":"10.1145\/73007.73040"},{"key":"40_CR10","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"S. Huddleston, K. Mehlhorn, \u201cA new data structure for representing sorted lists\u201d, Acta Informatica 17 (1982), 157\u2013184.","journal-title":"Acta Informatica"},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"J. A. La Poutr\u00e9, \u201cLower bounds for the union-find and the split-find problem on pointer machines\u201d, Proc. 22nd Annual ACM Symposium on Theory of Computing, 1990, 34\u201344.","DOI":"10.1145\/100216.100221"},{"key":"40_CR12","first-page":"122","volume-title":"Proc. 3rd International Conference on Logic Programming, Lecture Notes in Computer Science 225","author":"H. Mannila","year":"1986","unstructured":"H. Mannila, E. Ukkonen, \u201cOn the complexity of unification sequences\u201d, Proc. 3rd International Conference on Logic Programming, Lecture Notes in Computer Science 225, Springer-Verlag, Berlin, 1986, 122\u2013133."},{"key":"40_CR13","first-page":"34","volume-title":"Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT 88), Lecture Notes in Computer Science vol. 318","author":"H. Mannila","year":"1988","unstructured":"H. Mannila, E. Ukkonen, \u201cTime parameter and arbitrary deunions in the set union problem\u201d, Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT 88), Lecture Notes in Computer Science vol. 318, Springer-Verlag, Berlin, 1988, 34\u201342."},{"key":"40_CR14","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak, R. E. Tarjan, \u201cPlanar point location using persistent search trees\u201d, Comm. ACM 29 (1986), 669\u2013679.","journal-title":"Comm. ACM"},{"key":"40_CR15","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan, \u201cEfficiency of a good but not linear set union algorithm\u201d, J. Assoc. Comput. Mach. 22 (1975), 215\u2013225.","journal-title":"J. Assoc. Comput. Mach."},{"key":"40_CR16","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, \u201cA class of algorithms which require non linear time to maintain disjoint sets\u201d, J. Comput. Syst. Sci. 18 (1979), 110\u2013127.","journal-title":"J. Comput. Syst. Sci."},{"key":"40_CR17","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan, \u201cAmortized computational complexity\u201d, SIAM J. Alg. Disc. Meth. 6 (1985), 306\u2013318.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"40_CR18","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, \u201cWorst-case analysis of set union algorithms\u201d, J. Assoc. Comput. Mach. 31 (1984), 245\u2013281.","journal-title":"J. Assoc. Comput. Mach."},{"key":"40_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, \u201cProlog \u2014 the language and its implementation compared with LISP\u201d, ACM SIGPLAN Notices 12 (1977), 109\u2013115.","journal-title":"ACM SIGPLAN Notices"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028283.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:58:44Z","timestamp":1607551124000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540543430"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0028283","relation":{},"subject":[]}}