{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:08:34Z","timestamp":1672261714832},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1991,9,1]],"date-time":"1991-09-01T00:00:00Z","timestamp":683683200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1991,9]]},"DOI":"10.1007\/bf01933257","type":"journal-article","created":{"date-parts":[[2005,7,25]],"date-time":"2005-07-25T14:30:51Z","timestamp":1122301851000},"page":"381-393","source":"Crossref","is-referenced-by-count":3,"title":["The set union problem with dynamic weighted backtracking"],"prefix":"10.1007","volume":"31","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":"BF01933257_CR1","unstructured":"A. V. Aho, J. E. Hopcroft, J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974."},{"key":"BF01933257_CR2","doi-asserted-by":"crossref","unstructured":"M. L. Fredman, M. E. Saks,The cell probe complexity of dynamic data structures, Proc. 21st Annual ACM Symp. on Theory of Computing, 1989, 345\u2013354.","DOI":"10.1145\/73007.73040"},{"key":"BF01933257_CR3","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman, R. E. Tarjan,Fibonacci heaps and their uses in improved network optimization algorithms, J. Assoc. Comput. Mach. 34 (1987), 596\u2013615.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01933257_CR4","doi-asserted-by":"crossref","unstructured":"Z. Galil, G. F. Italiano,Data structures and algorithms for disjoint set union problems, ACM Comput. Surveys, to appear.","DOI":"10.1145\/116873.116878"},{"key":"BF01933257_CR5","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0022-0000(80)90035-5","volume":"21","author":"Z. Galil","year":"1980","unstructured":"Z. Galil, A. Naamad, An O (EVlog 2 V) algorithm for the maximal flow problem, J. Comput. Syst. Sci. 21 (1980), 203\u2013217.","journal-title":"J. Comput. Syst. Sci."},{"key":"BF01933257_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1007\/BFb0035827","volume-title":"Getting back to the past in the Union-find problem","author":"G. Gambosi","year":"1988","unstructured":"G. Gambosi, G. F. Italiano, M. Talamo,Getting back to the past in the Union-find problem, Proc. 5th Symp. on Theoretical Aspects of Computer Science, 1988, Lecture Notes in Computer Science, vol. 294, Springer-Verlag, Berlin, 8\u201317."},{"key":"BF01933257_CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0304-3975(89)90119-9","volume":"68","author":"G. Gambosi","year":"1989","unstructured":"G. Gambosi, G. F. Italiano, M. Talamo,Worst case analysis of the set union problem with extended backtracking, Theoret. Comput. Sci. 68 (1989), 57\u201370.","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"BF01933257_CR8","first-page":"313","volume":"7","author":"T. Ibaraki","year":"1978","unstructured":"T. Ibaraki,M-depth search in branch and bound algorithms, Int. J. Comp. Inform. Sc., 7, 4(1978), 313\u2013373.","journal-title":"Int. J. Comp. Inform. Sc."},{"key":"BF01933257_CR9","doi-asserted-by":"crossref","unstructured":"La Poutr\u00e9, J. A.,Lower bounds for the union-find and the split-find problem on pointer machines, Proc. 22nd Annual ACM Symp. on Theory of Computing, 1990, 34\u201344.","DOI":"10.1145\/100216.100221"},{"key":"BF01933257_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/3-540-16761-7_73","volume-title":"The set union problem with backtracking","author":"H. Mannila","year":"1986","unstructured":"H. Mannila, E. Ukkonen,The set union problem with backtracking, Proc. 13th Internat. Colloquium on Algebra, Languages and Programming, 1986, Lecture Notes in Computer Science, vol. 226, Springer-Verlag, Berlin, 236\u2013243."},{"key":"BF01933257_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/3-540-19487-8_4","volume-title":"Time parameter and arbitrary deunions in the set union problem","author":"H. Mannila","year":"1988","unstructured":"H. Mannila, E. Ukkonen,Time parameter and arbitrary deunions in the set union problem, Proc. 1st Scandinavian Workshop on Algorithm Theory, 1988, Lecture Notes in Computer Science vol. 318, Springer Verlag, Berlin, 34\u201342."},{"key":"BF01933257_CR12","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1137\/0217070","volume":"17","author":"K. Mehlhorn","year":"1988","unstructured":"K. Mehlhorn, S. Naher, H. Alt,A lower bound for the complexity of the union-split-find problem, SIAM J. Comput. 17 (1988), 1093\u20131102.","journal-title":"SIAM J. Comput."},{"key":"BF01933257_CR13","volume-title":"Heuristics","author":"J. Pearl","year":"1984","unstructured":"J. Pearl,Heuristics, Addison-Wesley, Reading, MA, 1984."},{"key":"BF01933257_CR14","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 set union algorithm, J. Assoc. Comput. Mach. 22 (1975), 215\u2013225.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01933257_CR15","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. Comput. Syst. Sci. 18 (1979), 110\u2013127.","journal-title":"J. Comput. Syst. Sci."},{"key":"BF01933257_CR16","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. Discr. Meth. 6 (1985), 306\u2013318.","journal-title":"SIAM J. Alg. Discr. Meth."},{"key":"BF01933257_CR17","unstructured":"R. E. Tarjan, Personal Communication, 1988."},{"key":"BF01933257_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,Worst-case analysis of set union algorithms, J. Assoc. Comput. Mach. 31 (1984), 245\u2013281.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01933257_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 - the language and its implementation compared with LISP, ACM SIGPLAN Notices 12 (1977), 109\u2013115.","journal-title":"ACM SIGPLAN Notices"},{"key":"BF01933257_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0218001","volume":"18","author":"J. Westbrook","year":"1989","unstructured":"J. Westbrook, R. E. Tarjan,Amortized analysis of algorithms for set union with backtracking, SIAM J. Comput. 18 (1989), 1\u201311.","journal-title":"SIAM J. Comput."}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01933257.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01933257\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01933257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T01:09:47Z","timestamp":1557450587000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01933257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["BF01933257"],"URL":"https:\/\/doi.org\/10.1007\/bf01933257","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}