{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:47:45Z","timestamp":1725662865800},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540088608"},{"type":"electronic","value":"9783540358077"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1978]]},"DOI":"10.1007\/3-540-08860-1_15","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T11:33:47Z","timestamp":1330169627000},"page":"192-204","source":"Crossref","is-referenced-by-count":3,"title":["Time and space bounds for selection problems"],"prefix":"10.1007","author":[{"given":"David","family":"Dobkin","sequence":"first","affiliation":[]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"15_CR1","unstructured":"B. Allen, \"On Binary Search Trees,\" Research Report CS-77-27, Department of Computer Science, University of Waterloo."},{"key":"15_CR2","unstructured":"Bayer, P. J., \"Improved Bounds of the Costs of Optimal and Balanced Binary Search Trees,\" Project MAC Technical Memorandum 69, M.I.T., November 1975."},{"key":"15_CR3","first-page":"448","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M. Floyd, R., Pratt, V., Rivest, R., and Tarjan, R., \"Time Bounds for Selection,\" JCSS 7(1973), pp. 448\u2013461.","journal-title":"JCSS"},{"key":"15_CR4","unstructured":"Dobkin, D., and Munro, I., \"A Minimal Space Selection Algorithm that Runs in Linear Time,\u2019 Proc. Johns Hopkins CISS Conference April 1977. Also appears as Yale Department of Computer Science Technical Report #106."},{"issue":"1","key":"15_CR5","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1137\/0201004","volume":"1","author":"F. K. Hwang","year":"1972","unstructured":"Hwang, F. K. and Lin, S., \"A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets,\" SICOMP 1,1(March 1972), pp. 31\u201339.","journal-title":"SICOMP"},{"issue":"1","key":"15_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0205001","volume":"5","author":"I. Munro","year":"1976","unstructured":"Munro, I. and Spira, P., \"Sorting and Searching in Multisets,\" SICOMP 5,1 (March 1976), pp. 1\u20139.","journal-title":"SICOMP"},{"key":"15_CR7","unstructured":"Pohl, I., \"A Minimum Storage Algorithm for Computing the Median\", IBM Technical Report RC2701, November 1969."},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Pratt, V., and Yao, F., \"On Lower Bounds for Computing the ith Largest Element,\" Proc. 14th IEEE Symposium on SWAT, October 1973, pp. 70\u201381.","DOI":"10.1109\/SWAT.1973.18"},{"key":"15_CR9","unstructured":"Rivest, R. and Floyd, R., \"Bounds on the Expected Time for Median Computations,\" in Combinatorial Algorithms ed. R. Rustin, Courant C. S. Symposium 9, Algorithmics Press 1973, see also Rivest and Floyd \"Algorithm 488 (Select) CACM 18(1975), p. 173."},{"key":"15_CR10","first-page":"184","volume":"13","author":"A. Schonage","year":"1976","unstructured":"Schonage, A. Paterson, M. and Pippenger, N., \"Finding the Median,\" JCSS 13 (1976), pp. 184\u2013199.","journal-title":"JCSS"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08860-1_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:00:01Z","timestamp":1605625201000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08860-1_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1978]]},"ISBN":["9783540088608","9783540358077"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-08860-1_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1978]]}}}