{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:28:54Z","timestamp":1761611334640},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_20","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T03:22:47Z","timestamp":1376623367000},"page":"229-240","source":"Crossref","is-referenced-by-count":4,"title":["The Encoding Complexity of Two Dimensional Range Minimum Data Structures"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrej","family":"Brodnik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pooya","family":"Davoodi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","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)"},{"issue":"4","key":"20_CR2","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1007\/s00453-011-9499-0","volume":"63","author":"G.S. Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica\u00a063(4), 815\u2013830 (2012)","journal-title":"Algorithmica"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Rosenberg, B.: Computing partial sums in multidimensional arrays. In: Mehlhorn, K. (ed.) SoCG, pp. 131\u2013139. ACM (1989)","DOI":"10.1145\/73833.73848"},{"key":"20_CR4","unstructured":"Davoodi, P.: Data Structures: Range Queries and Space Efficiency. PhD thesis, Aarhus University, Aarhus, Denmark (2011)"},{"key":"20_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/978-3-642-32241-9_34","volume-title":"Computing and Combinatorics","author":"P. Davoodi","year":"2012","unstructured":"Davoodi, P., Raman, R., Rao, S.S.: Succinct representations of binary trees for range minimum queries. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol.\u00a07434, pp. 396\u2013407. Springer, Heidelberg (2012)"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-642-02927-1_29","volume-title":"Automata, Languages and Programming","author":"E.D. Demaine","year":"2009","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, Part I. LNCS, vol.\u00a05555, pp. 341\u2013353. Springer, Heidelberg (2009)"},{"issue":"2","key":"20_CR7","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J. Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput.\u00a040(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: DeMillo, R.A. (ed.) STOC, pp. 135\u2013143. ACM (1984)","DOI":"10.1145\/800057.808675"},{"issue":"2","key":"20_CR9","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 J. Comput.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"20_CR10","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. J. Discrete Algorithms\u00a05(1), 12\u201322 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Yuan, H., Atallah, M.J.: Data structures for range minimum queries in multidimensional arrays. In: Charikar, M. (ed.) SODA, pp. 150\u2013160. SIAM (2010)","DOI":"10.1137\/1.9781611973075.14"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T17:13:06Z","timestamp":1558026786000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}