{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:02Z","timestamp":1742596802939,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571551"},{"type":"electronic","value":"9783540479185"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57155-8_246","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:05:16Z","timestamp":1330257916000},"page":"175-187","source":"Crossref","is-referenced-by-count":3,"title":["Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs"],"prefix":"10.1007","author":[{"given":"O.","family":"Berkman","sequence":"first","affiliation":[]},{"given":"Y.","family":"Matias","sequence":"additional","affiliation":[]},{"given":"P.","family":"Ragde","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"18_CR1","unstructured":"A. Amir, G. M. Landau, and U. Vishkin. Efficient pattern matching with scaling. In Proc. of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 344\u2013357, 1990."},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"P. Beame and J. H\u00e5stad. Optimal bounds for decision problems on the CRCW PRAM. In Proc. of the 19th Ann. ACM Symp. on Theory of Computing, pages 83\u201393, 1987.","DOI":"10.1145\/28395.28405"},{"key":"18_CR3","unstructured":"C. Berge. Graphs and Hypergraphs. North-Holland, 1973."},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"O. Berkman, J. J\u00e1J\u00e1, S. Krishnamurthy, R. Thurimella, and U. Vishkin. Some triply-logarithmic parallel algorithms. In Proc. of the 31st IEEE Annual Symp. on Foundation of Computer Science, pages 871\u2013881, 1990. To appear in SIAM J. of Comput. as \u2018Top-bottom routing around a rectangle is as easy as computing prefix minima'.","DOI":"10.1109\/FSCS.1990.89611"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1006\/jagm.1993.1018","volume":"14","author":"O. Berkman","year":"1993","unstructured":"O. Berkman, B. Schieber, and U. Vishkin. Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. Journal of Algorithms, 14:344\u2013370, 1993.","journal-title":"Journal of Algorithms"},{"key":"18_CR6","unstructured":"O. Berkman and U. Vishkin. On parallel integer merging. Technical Report UMIACS-TR-90-15.1 (revised version), Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742, USA, 1990. To appear in Information and Computation."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"R. B. Boppana. Optimal separations between concurrent-write parallel machines. In Proc. of the 21st Ann. ACM Symp. on Theory of Computing, pages 320\u2013326, 1989.","DOI":"10.1145\/73007.73037"},{"key":"18_CR8","unstructured":"S. Chaudhuri. Lower Bounds for Parallel Computation. PhD thesis, Rutgers University, 1991."},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"J. Edmonds. Lower bounds with smaller domain size on concurrent write parallel machines. In Proc. 6th Annual IEEE Conference on Structure in Complexity Theory, 1991.","DOI":"10.1109\/SCT.1991.160276"},{"key":"18_CR10","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P. Erd\u0151s","year":"1960","unstructured":"P. Erd\u0151s and R. Rado. Intersection theorems for systems of sets. J. London Math. Soc., 35:85\u201390, 1960.","journal-title":"J. London Math. Soc."},{"key":"18_CR11","unstructured":"F. E. Fich, F. Meyer auf der Heide, and A. Wigderson. Lower bounds for parallel random-access machines with unbounded shared memory. In Advances in Computing Research. JAI Press, 1986."},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"F. E. Fich, P. L. Ragde, and A. Wigderson. Relations between concurrent-write models of parallel computation (preliminary version). In Proceedings 3rd Annual ACM Symposium on Principles of Distributed Computing, pages 179\u2013189, 1984.","DOI":"10.1145\/800222.806745"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/BF01762109","volume":"3","author":"F. E. Fich","year":"1988","unstructured":"F. E. Fich, P. L. Ragde, and A. Wigderson. Simulations among concurrent-write PRAMs. Algorithmica, 3:43\u201351, 1988.","journal-title":"Algorithmica"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, J. L. Bentley, and R. E. Tarjan. Scaling and related techniques for geometry problems. In Proc. of the 16th Ann. ACM Symp. on Theory of Computing, pages 135\u2013143, 1984.","DOI":"10.1145\/800057.808675"},{"key":"18_CR15","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0196-6774(89)90032-1","volume":"10","author":"M. T. Goodrich","year":"1989","unstructured":"M. T. Goodrich. Triangulating a polygon in parallel. Journal of Algorithms, 10:327\u2013351, 1989.","journal-title":"Journal of Algorithms"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"V. Grolmusz and P. L. Ragde. Incomparability in parallel computation. In Proc. of the 28th IEEE Annual Symp. on Foundation of Computer Science, pages 89\u201398, 1987.","DOI":"10.1109\/SFCS.1987.34"},{"issue":"2","key":"18_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":"18_CR18","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"C-32","author":"C. P. Kruskal","year":"1983","unstructured":"C. P. Kruskal. Searching, merging, and sorting in parallel computation. IEEE Trans. on Comp, C-32:942\u2013946, 1983.","journal-title":"IEEE Trans. on Comp"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide and A. Wigderson. The complexity of parallel sorting. In Proc. of the 26th IEEE Annual Symp. on Foundation of Computer Science, pages 532\u2013540, 1985.","DOI":"10.1109\/SFCS.1985.58"},{"issue":"3","key":"18_CR20","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1137\/0401040","volume":"1","author":"P. L. Ragde","year":"1988","unstructured":"P. L. Ragde, W. L. Steiger, E. Szemer\u00e9di, and A. Wigderson. The parallel complexity of element distinctness is \u03a9(\u221alog n). SIAM Journal on Disceret Mathematics, 1(3):399\u2013410, Aug. 1988.","journal-title":"SIAM Journal on Disceret Mathematics"},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"V. Ramachandran and U. Vishkin. Efficient parallel triconnectivity in logarithmic parallel time. In Proc. of the 3rd Aegean Workshop on Parallel Computing, Springer LNCS 319, pages 33\u201342, 1988.","DOI":"10.1007\/BFb0040371"},{"key":"18_CR22","unstructured":"B. Schieber. Design and analysis of some parallel algorithms. PhD thesis, Dept. of Computer Science, Tel Aviv Univ., 1987."},{"issue":"6","key":"18_CR23","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin. On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput., 17(6):1253\u20131262, 1988.","journal-title":"SIAM J. Comput."},{"key":"18_CR24","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. Journal of Algorithms, 2:88\u2013102, 1981.","journal-title":"Journal of Algorithms"},{"key":"18_CR25","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1137\/0214051","volume":"14","author":"M. Snir","year":"1985","unstructured":"M. Snir. On parallel searching. SIAM J. Comput., 14:688\u2013707, 1985.","journal-title":"SIAM J. Comput."},{"key":"18_CR26","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."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_246.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:59:50Z","timestamp":1742594390000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_246","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}