{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:55:57Z","timestamp":1725663357821},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540529217"},{"type":"electronic","value":"9783540471776"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52921-7_61","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:47:38Z","timestamp":1330206458000},"page":"118-127","source":"Crossref","is-referenced-by-count":1,"title":["Two probabilistic results on merging"],"prefix":"10.1007","author":[{"given":"Wenceslas Fernandez","family":"Vega","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sampath","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"C. Christen (1978) Improving the bound on optimal merging, Proceedings of 19th FOCS, pp. 259\u2013266.","DOI":"10.1109\/SFCS.1978.20"},{"key":"13_CR2","unstructured":"C. Christen (1978) On the optimality of the straight merging algorithm, Publication 296, D\u00e9p. d'Info. et de Rech. Op., Universit\u00e9 de Montr\u00e9al."},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01874387","volume":"1","author":"V. Chvatal","year":"1984","unstructured":"V. Chvatal (1984) Probabilistic methods in graph theory, Annals of Operations Research 1, pp. 171\u2013182.","journal-title":"Annals of Operations Research"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF00289521","volume":"1","author":"F. K. Hwang","year":"1971","unstructured":"F. K. Hwang and S. Lin (1971), Optimal merging of 2 elements with n elements, Acta Informatica 1, pp. 145\u2013158.","journal-title":"Acta Informatica"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/0201004","volume":"1","author":"F. K. Hwang","year":"1972","unstructured":"F. K. Hwang and S. Lin (1972), A simple algorithm for merging two disjoint linearly ordered lists, SIAM J. of Comput. 1, pp. 31\u201339.","journal-title":"SIAM J. of Comput."},{"issue":"1","key":"13_CR6","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1145\/321738.321749","volume":"20","author":"F. K. Hwang","year":"1973","unstructured":"F. K. Hwang and D. N. Deutsch (1973) A class of merging algorithms, JACM, Vol. 20, No. 1, pp. 148\u2013159.","journal-title":"JACM"},{"key":"13_CR7","unstructured":"D. E. Knuth (1973), The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley."},{"issue":"3","key":"13_CR8","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1145\/322139.322144","volume":"26","author":"G. K. Manacher","year":"1979","unstructured":"G. K. Manacher (1979), Significant improvements to the Hwang-Ling merging algorithm, JACM, Vol. 26, No. 3, pp. 434\u2013440.","journal-title":"JACM"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1137\/0209006","volume":"9","author":"P. K. Stockmeyer","year":"1980","unstructured":"P. K. Stockmeyer and F. F. Yao (1980) On the optimality of linear merge, SIAM J of Comput. 9, pp. 85\u201390.","journal-title":"SIAM J of Comput."},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"A. Yao (1977), Probabilistic computations: Towards a unified mesure of complexity, Proc. 18th FOCS, pp. 222\u2013227.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52921-7_61.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:10:07Z","timestamp":1619572207000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52921-7_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540529217","9783540471776"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-52921-7_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}