{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:07:26Z","timestamp":1787508446956,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642157806","type":"print"},{"value":"9783642157813","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15781-3_15","type":"book-chapter","created":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T07:40:03Z","timestamp":1283326803000},"page":"171-182","source":"Crossref","is-referenced-by-count":8,"title":["On Space Efficient Two Dimensional Range Minimum Data Structures"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pooya","family":"Davoodi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"15_CR1","first-page":"253","volume-title":"Proc. 5th Annual ACM Symposium on Theory of Computing","author":"A. Aho","year":"1973","unstructured":"Aho, A., Hopcroft, J., Ullman, J.: On finding lowest common ancestors in trees. In: Proc. 5th Annual ACM Symposium on Theory of Computing, pp. 253\u2013265. ACM Press, New York (1973)"},{"key":"15_CR2","first-page":"258","volume-title":"Proc. 14th Annual ACM Symposium on Parallel Algorithms and Architectures","author":"S. Alstrup","year":"2002","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: a survey and a new distributed algorithm. In: Proc. 14th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 258\u2013264. ACM, New York (2002)"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/978-3-540-73437-6_29","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2007","unstructured":"Amir, A., Fischer, J., Lewenstein, M.: Two-dimensional range minimum queries. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 286\u2013294. Springer, Heidelberg (2007)"},{"key":"15_CR4","first-page":"150","volume-title":"Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M.J. Atallah","year":"2010","unstructured":"Atallah, M.J., Yuan, H.: Data structures for range minimum queries in multidimensional arrays. In: Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 150\u2013160. SIAM, Philadelphia (2010)"},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M. Bender","year":"2000","unstructured":"Bender, M., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"issue":"2","key":"15_CR6","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. Journal of Algorithms\u00a057(2), 75\u201394 (2005)","journal-title":"Journal of Algorithms"},{"issue":"5","key":"15_CR7","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J.L. Bentley","year":"1979","unstructured":"Bentley, J.L.: Decomposable searching problems. Information Processing Letters\u00a08(5), 244\u2013251 (1979)","journal-title":"Information Processing Letters"},{"key":"15_CR8","first-page":"309","volume-title":"Proc. 21st Ann. ACM Symposium on Theory of Computing","author":"O. Berkman","year":"1989","unstructured":"Berkman, O., Galil, Z., Schieber, B., Vishkin, U.: Highly parallelizable problems. In: Proc. 21st Ann. ACM Symposium on Theory of Computing, pp. 309\u2013319. ACM, New York (1989)"},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1145\/73833.73848","volume-title":"Proc. 5th Annual Symposium on Computational Geometry","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B., Rosenberg, B.: Computing partial sums in multidimensional arrays. In: Proc. 5th Annual Symposium on Computational Geometry, pp. 131\u2013139. ACM, New York (1989)"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On cartesian trees and range minimum queries. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 341\u2013353. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-02927-1_29"},{"key":"15_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/978-3-642-12200-2_16","volume-title":"Proc. 9th Latin American Theoretical Informatics Symposium","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 158\u2013169. Springer, Heidelberg (2010)"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-3-540-74450-4_41","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"J. Fischer","year":"2007","unstructured":"Fischer, J., Heun, V.: A new succinct representation of rmq-information and improvements in the enhanced suffix array. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol.\u00a04614, pp. 459\u2013470. Springer, Heidelberg (2007)"},{"key":"15_CR13","first-page":"135","volume-title":"Proc. 16th Annual ACM Symposium on Theory of Computing","author":"H.N. Gabow","year":"1984","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th Annual ACM Symposium on Theory of Computing, pp. 135\u2013143. ACM, New York (1984)"},{"issue":"2","key":"15_CR14","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR15","unstructured":"Miltersen, P.B.: Cell probe complexity - a survey. In: Advances in Data Structures Workshop (FSTTCS) (1999)"},{"issue":"1","key":"15_CR16","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. Journal of Discrete Algorithms\u00a05(1), 12\u201322 (2007)","journal-title":"Journal of Discrete Algorithms"},{"issue":"6","key":"15_CR17","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"Schieber, B., Vishkin, U.: On finding lowest common ancestors: simplification and parallelization. SIAM Journal on Computing\u00a017(6), 1253\u20131262 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"15_CR18","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J. Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Communications of the ACM\u00a023(4), 229\u2013239 (1980)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15781-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T01:25:09Z","timestamp":1552958709000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15781-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157806","9783642157813"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15781-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}