{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:28:31Z","timestamp":1761611311312},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642322402"},{"type":"electronic","value":"9783642322419"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32241-9_34","type":"book-chapter","created":{"date-parts":[[2012,8,13]],"date-time":"2012-08-13T15:12:12Z","timestamp":1344870732000},"page":"396-407","source":"Crossref","is-referenced-by-count":15,"title":["Succinct Representations of Binary Trees for Range Minimum Queries"],"prefix":"10.1007","author":[{"given":"Pooya","family":"Davoodi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"34_CR1","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D. Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica\u00a043(4), 275\u2013292 (2005)","journal-title":"Algorithmica"},{"key":"34_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-540-69903-3_17","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"A. Farzan","year":"2008","unstructured":"Farzan, A., Munro, J.I.: A Uniform Approach Towards Succinct Representation of Trees. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol.\u00a05124, pp. 173\u2013184. Springer, Heidelberg (2008)"},{"key":"34_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-642-02927-1_38","volume-title":"Automata, Languages and Programming","author":"A. Farzan","year":"2009","unstructured":"Farzan, A., Raman, R., Rao, S.S.: Universal Succinct Representations of Trees? In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 451\u2013462. Springer, Heidelberg (2009)"},{"key":"34_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-12200-2_16","volume-title":"LATIN 2010: Theoretical Informatics","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)"},{"issue":"2","key":"34_CR5","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 Journal on Computing\u00a040(2), 465\u2013492 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR6","doi-asserted-by":"crossref","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 Press (1984)","DOI":"10.1145\/800057.808675"},{"issue":"3","key":"34_CR7","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.tcs.2006.09.014","volume":"368","author":"R.F. Geary","year":"2006","unstructured":"Geary, R.F., Rahman, N., Raman, R., Raman, V.: A simple optimal representation for balanced parentheses. Theoretical Computer Science\u00a0368(3), 231\u2013246 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"34_CR8","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/1198513.1198516","volume":"2","author":"R.F. Geary","year":"2006","unstructured":"Geary, R.F., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. ACM Transactions on Algorithms\u00a02(4), 510\u2013534 (2006)","journal-title":"ACM Transactions on Algorithms"},{"key":"34_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-25591-5_20","volume-title":"Algorithms and Computation","author":"M. Golin","year":"2011","unstructured":"Golin, M., Iacono, J., Krizanc, D., Raman, R., Rao, S.S.: Encoding 2D Range Maximum Queries. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 180\u2013189. Springer, Heidelberg (2011)"},{"issue":"2","key":"34_CR10","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":"34_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/978-3-540-73420-8_45","volume-title":"Automata, Languages and Programming","author":"M. He","year":"2007","unstructured":"He, M., Munro, J.I.J., Rao, S.S.: Succinct Ordinal Trees Based on Tree Covering. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 509\u2013520. Springer, Heidelberg (2007)"},{"key":"34_CR12","unstructured":"Jacobson, G.: Succinct Static Data Structures. PhD thesis. Carnegie Mellon University, Pittsburgh, PA, USA (1989)"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"Lu, H.-I., Yeh, C.-C.: Balanced parentheses strike back. ACM Transactions on Algorithms\u00a04(3) (2008)","DOI":"10.1145\/1367064.1367068"},{"issue":"3","key":"34_CR14","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM Journal on Computing\u00a031(3), 762\u2013776 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR15","unstructured":"Munro, J.I., Raman, V., Storm, A.J.: Representing dynamic binary trees succinctly. In: Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 529\u2013536. SIAM (2001)"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms\u00a03(4) (2007)","DOI":"10.1145\/1290672.1290680"},{"key":"34_CR17","unstructured":"Sadakane, K.: Succinct representations of lcp information and improvements in the compressed suffix arrays. In: Proc. 13th Symposium on Discrete Algorithms, pp. 225\u2013232 (2002)"},{"issue":"1","key":"34_CR18","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"},{"key":"34_CR19","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 134\u2013149. SIAM (2010)","DOI":"10.1137\/1.9781611973075.13"},{"issue":"4","key":"34_CR20","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","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32241-9_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:58:55Z","timestamp":1620129535000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32241-9_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642322402","9783642322419"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32241-9_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}