{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T06:56:24Z","timestamp":1747810584867},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571827"},{"type":"electronic","value":"9783540479277"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57182-5_27","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:10:11Z","timestamp":1330258211000},"page":"352-361","source":"Crossref","is-referenced-by-count":12,"title":["Approximate and exact deterministic parallel selection"],"prefix":"10.1007","author":[{"given":"Shiva","family":"Chaudhuri","sequence":"first","affiliation":[]},{"given":"Torben","family":"Hagerup","sequence":"additional","affiliation":[]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0022-0000(89)90035-4","volume":"38","author":"M. Ajtai","year":"1989","unstructured":"M. Ajtai, J. Koml\u00f3s, W. L. Steiger, and E. Szemer\u00e9di. Optimal parallel selection has complexity O(log log N). Journal of Computer and System Sciences, 38 (1989), pp. 125\u2013133.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di. An O(n log n) sorting network. In Proc. 15th ACM STOC (1983), pp. 1\u20139.","DOI":"10.1145\/800061.808726"},{"key":"27_CR3","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01206355","volume":"11","author":"N. Alon","year":"1991","unstructured":"N. Alon and Y. Azar. Parallel Comparison Algorithms for Approximation Problems. Combinatorica, 11 (1991), pp. 97\u2013122.","journal-title":"Combinatorica"},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0166-218X(90)90128-Y","volume":"27","author":"Y. Azar","year":"1990","unstructured":"Y. Azar and N. Pippenger. Parallel selection. Discrete Applied Mathematics, 27 (1990), pp. 49\u201358.","journal-title":"Discrete Applied Mathematics"},{"key":"27_CR5","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1145\/65950.65958","volume":"36","author":"P. Beame","year":"1989","unstructured":"P. Beame and J. H\u00e5stad. Optimal bounds for decision problems on the CRCW PRAM. Journal of the ACM, 36 (1989), pp. 643\u2013670.","journal-title":"Journal of the ACM"},{"key":"27_CR6","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7 (1973), pp. 448\u2013461.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR7","unstructured":"V. Chvatal. Lecture notes on the new AKS sorting network. DIMACS Technical Report 92\u201329, 1992."},{"key":"27_CR8","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole. Parallel merge sort. SIAM Journal on Computing, 17 (1988), pp. 770\u2013785.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR9","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0020-0190(88)90186-X","volume":"26","author":"R. Cole","year":"1988","unstructured":"R. Cole. An optimally efficient selection algorithm. Information Processing Letters, 26 (1988), pp. 295\u2013299.","journal-title":"Information Processing Letters"},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/0890-5401(89)90036-9","volume":"81","author":"R. Cole","year":"1989","unstructured":"R. Cole and U. Vishkin. Faster optimal parallel prefix sums and list ranking. Information and Computation, 81 (1989), pp. 334\u2013352.","journal-title":"Information and Computation"},{"key":"27_CR11","unstructured":"P. F. Dietz and R. Raman. Heap construction on the CRCW PRAM. In preparation, 1993."},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich. Using approximation algorithms to design parallel algorithms that may ignore processor allocation. In Proc. 32nd IEEE FOCS (1991), pp. 711\u2013722.","DOI":"10.1109\/SFCS.1991.185439"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"T. Hagerup. The log-star revolution. In Proc. 9th STACS (1992), LNCS 577, pp. 259\u2013278.","DOI":"10.1007\/3-540-55210-3_189"},{"key":"27_CR14","unstructured":"T. Hagerup. Fast deterministic processor allocation. In Proc. 4th ACM-SIAM SODA (1993), pp. 1\u201310."},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"T. Hagerup and R. Raman. Waste makes haste: Tight bounds for loose parallel sorting. In Proc. 33rd IEEE FOCS (1992), pp. 628\u2013637.","DOI":"10.1109\/SFCS.1992.267788"},{"key":"27_CR16","doi-asserted-by":"crossref","unstructured":"T. Hagerup and R. Raman. Fast deterministic approximate and exact parallel sorting. In Proc. 5th ACM SPAA (1993), to appear.","DOI":"10.1145\/165231.157380"},{"key":"27_CR17","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF01840378","volume":"5","author":"M. S. Paterson","year":"1990","unstructured":"M.S. Paterson. Improved sorting networks with O(log N) depth. Algorithmica, 5 (1990), pp. 75\u201392.","journal-title":"Algorithmica"},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"N. Pippenger. Communication Networks. In Handbook of Theoretical Computer Science, Vol A, Algorithms and Complexity (J. van Leeuwen, ed.). Elsevier\/The MIT Press (1990), Chapter 15, pp. 805\u2013833.","DOI":"10.1016\/B978-0-444-88071-0.50020-5"},{"key":"27_CR19","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1137\/0214030","volume":"14","author":"R. Reischuk","year":"1985","unstructured":"R. Reischuk. Probabilistic parallel algorithms for sorting and selection. SIAM Journal on Computing, 14 (1985), pp. 396\u2013409.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR20","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. G. Valiant","year":"1975","unstructured":"L. G. Valiant. Parallelism in comparison problems. SIAM Journal on Computing, 4 (1975), pp. 348\u2013355.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1993"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57182-5_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T00:59:30Z","timestamp":1619571570000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57182-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571827","9783540479277"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-57182-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}