{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:29Z","timestamp":1742617169201,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540562795"},{"type":"electronic","value":"9783540475019"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56279-6_66","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:57:27Z","timestamp":1330253847000},"page":"135-144","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Randomized range-maxima in nearly-constant parallel time"],"prefix":"10.1007","author":[{"given":"Omer","family":"Berkman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yossi","family":"Matias","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uzi","family":"Vishkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"1178","DOI":"10.1137\/0217074","volume":"17","author":"N. Alon","year":"1988","unstructured":"N. Alon and Y. Azar. The average complexity of deterministic and randomized parallel comparison-sorting algorithms. SIAM J. Comput., 17:1178\u20131192, 1988.","journal-title":"SIAM J. Comput."},{"key":"15_CR2","unstructured":"N. Alon and B. Schieber. Optimal preprocessing for answering on-line product queries. Technical Report 71\/87, Eskenasy Inst. of Comp. Sc., Tel Aviv Univ., 1987."},{"key":"15_CR3","unstructured":"A. Amir, G. M. Landau, and U. Vishkin. Efficient pattern matching with scaling. In SODA '90, pages 344\u2013357, 1990."},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"D. Angluin and L. G. Valiant. Fast probabilistic algorithms for hamiltonian paths and matchings. J. Comput. Syst. Sci., 18:155\u2013193, 1979.","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1137\/0216032","volume":"16","author":"Y. Azar","year":"1987","unstructured":"Y. Azar and U. Vishkin. Tight comparison bounds on the complexity of parallel sorting. SIAM J. Comput., 16:458\u2013464, 1987.","journal-title":"SIAM J. Comput."},{"key":"15_CR6","unstructured":"O. Berkman, Y. Matias, and U. Vishkin. Randomized range-maxima in nearlyconstant parallel time. Technical Report UMIACS-TR-91-161, Institute for Advanced Computer Studies, Univ. of Maryland, 1991. To appear in j. computational complexity."},{"key":"15_CR7","unstructured":"O. Berkman, B. Schieber, and U. Vishkin. Some doubly logarithmic parallel algorithms based on finding all nearest smaller values. Technical Report UMIACS-TR-88-79, Univ. of Maryland Inst. for Advanced Computer Studies, Oct. 1988. To appear in J. Algorithms as \u2018Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values'."},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"O. Berkman and U. Vishkin. Recursive *-tree parallel data-structure. In FOCS '89, pages 196\u2013202, 1989. Also in UMIACS-TR-90-40, Institute for Advanced Computer Studies, Uniy. of Maryland, March 1991. To appear in SIAM J. Comput.","DOI":"10.1109\/SFCS.1989.63478"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0020-0190(89)90194-4","volume":"33","author":"R. B. Boppana","year":"1989","unstructured":"R. B. Boppana. The average-case parallel complexity of sorting. Inf. Process. Lett., 33:145\u2013146, 1989.","journal-title":"Inf. Process. Lett."},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(85)90008-X","volume":"30","author":"A. Borodin","year":"1985","unstructured":"A. Borodin and J. E. Hopcroft. Routing, merging, and sorting on parallel models of computation. J. Comput. Syst. Sci., 30:130\u2013145, 1985.","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR11","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Math. Statistics, 23:493\u2013507, 1952.","journal-title":"Annals of Math. Statistics"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"P. F. Dietz. Heap construction in the parallel comparison tree model. In SWAT '92, pages 140\u2013150, July 1992.","DOI":"10.1007\/3-540-55706-7_13"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, J. L. Bentley, and R. E. Tarjan. Scaling and related techniques for geometry problems. In STOC '84, pages 135\u2013143, 1984.","DOI":"10.1145\/800057.808675"},{"key":"15_CR14","unstructured":"J. Gil and Y. Matias. Fast hashing on a PRAM\u2014designing by expectation. In SODA '91, pages 271\u2013280, 1991."},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"J. Gil, Y. Matias, and U. Vishkin. Towards a theory of nearly constant time parallel algorithms. In FOCS '91, pages 698\u2013710, Oct. 1991.","DOI":"10.1109\/SFCS.1991.185438"},{"key":"15_CR16","unstructured":"J. Gil and L. Rudolph. Counting and packing in parallel. In ICPP '86, pages 1000\u20131002, 1986."},{"issue":"2","key":"15_CR17","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338\u2013355, 1984.","journal-title":"SIAM J. Comput."},{"key":"15_CR18","unstructured":"P. D. MacKenzie. Load balancing requires \u03a9(log* n) expected time. In SODA '92, pages 94\u201399, Jan. 1992."},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Y. Matias and U. Vishkin. Converting high probability into nearly-constant time\u2014with applications to parallel hashing. In STOC '91, pages 307\u2013316, 1991. Also in UMIACS-TR-91-65, Institute for Advanced Computer Studies, Univ. of Maryland, April 1991.","DOI":"10.1145\/103418.103453"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"V. Ramachandran and U. Vishkin. Efficient parallel triconnectivity in logarithmic parallel time. In AWOC '88, pages 33\u201342, 1988.","DOI":"10.1007\/BFb0040371"},{"issue":"2","key":"15_CR21","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 J. Comput., 14(2):396\u2013409, May 1985.","journal-title":"SIAM J. Comput."},{"key":"15_CR22","unstructured":"B. Schieber. Design and analysis of some parallel algorithms. PhD thesis, Dept. of Computer Science, Tel Aviv Univ., 1987."},{"key":"15_CR23","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin. Finding the maximum, merging, and sorting in a parallel computation model. J. of Alg., 2:88\u2013102, 1981.","journal-title":"J. of Alg."},{"issue":"2","key":"15_CR24","doi-asserted-by":"publisher","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. ACM, 22(2):215\u2013225, Apr. 1975.","journal-title":"J. ACM"},{"key":"15_CR25","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. G. Valiant","year":"1975","unstructured":"L. G. Valiant. Parallelism in comparison problems. SIAM J. Comput., 4:348\u2013355, 1975.","journal-title":"SIAM J. Comput."},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"U. Vishkin. Structural parallel algorithmics. In ICALP '91, pages 363\u2013380, 1991.","DOI":"10.1007\/3-540-54233-7_148"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56279-6_66","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:46:21Z","timestamp":1742593581000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56279-6_66"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540562795","9783540475019"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-56279-6_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}