{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T02:38:02Z","timestamp":1794364682274,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642029264","type":"print"},{"value":"9783642029271","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_38","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T04:37:10Z","timestamp":1246682230000},"page":"451-462","source":"Crossref","is-referenced-by-count":22,"title":["Universal Succinct Representations of Trees?"],"prefix":"10.1007","author":[{"given":"Arash","family":"Farzan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"4","key":"38_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":"38_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BFb0055046","volume-title":"Automata, Languages and Programming","author":"R.C. Chuang","year":"1998","unstructured":"Chuang, R.C., Garg, A., He, X., Kao, M., Lu, H.: Compact encodings of planar graphs via canonical orderings and multiple parentheses. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 118\u2013129. Springer, Heidelberg (1998)"},{"key":"38_CR3","series-title":"ACM Intl. Conference Proceeding Series","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/1353343.1353354","volume-title":"EDBT","author":"O. Delpratt","year":"2008","unstructured":"Delpratt, O., Raman, R., Rahman, N.: Engineering succinct DOM. In: EDBT. ACM Intl. Conference Proceeding Series, vol.\u00a0261, pp. 49\u201360. ACM Press, New York (2008)"},{"key":"38_CR4","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":"38_CR5","first-page":"184","volume-title":"FOCS","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: FOCS, pp. 184\u2013196. IEEE Computer Society Press, Los Alamitos (2005)"},{"issue":"4","key":"38_CR6","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":"38_CR7","volume-title":"Concrete Mathematics: A Foundation for Computer Science","author":"R.L. Graham","year":"1994","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Longman Publishing Co., Inc., Boston (1994)"},{"key":"38_CR8","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., 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":"38_CR9","unstructured":"Jacobson, G.J.: Succinct static data structures. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA (1988)"},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"Jacobson, G.J.: Space-efficient static trees and graphs. In: IEEE Symposium on Foundations of Computer Science, 1989, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"38_CR11","first-page":"575","volume-title":"SODA","author":"J. Jansson","year":"2007","unstructured":"Jansson, J., Sadakane, K., Sung, W.: Ultra-succinct representation of ordered trees. In: SODA, pp. 575\u2013584. SIAM, Philadelphia (2007)"},{"issue":"3","key":"38_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1367064.1367068","volume":"4","author":"H. Lu","year":"2008","unstructured":"Lu, H., Yeh, C.: Balanced parentheses strike back. ACM Trans. Algorithms\u00a04(3), 1\u201313 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses, static trees and planar graphs. In: IEEE Symposium on Foundations of Computer Science, pp. 118\u2013126 (1997)","DOI":"10.1109\/SFCS.1997.646100"},{"key":"38_CR14","first-page":"529","volume-title":"SODA","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V., Storm, A.J.: Representing dynamic binary trees succinctly. In: SODA, pp. 529\u2013536. SIAM, Philadelphia (2001)"},{"key":"38_CR15","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Rao, S.S.: Succinct Representation of Data Structures. In: Handbook of Data Structures and Applications, ch. 37, Chapman & Hall\/CRC (2004)","DOI":"10.1201\/9781420035179.ch37"},{"key":"38_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1007\/978-3-540-27836-8_84","volume-title":"Automata, Languages and Programming","author":"J.I. Munro","year":"2004","unstructured":"Munro, J.I., Rao, S.S.: Succinct representations of functions. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1006\u20131015. Springer, Heidelberg (2004)"},{"issue":"4","key":"38_CR17","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R. Raman","year":"2002","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms\u00a03(4), 43 (2002); Preliminary version in SODA 2002","journal-title":"ACM Transactions on Algorithms"},{"key":"38_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/3-540-45061-0_30","volume-title":"Automata, Languages and Programming","author":"R. Raman","year":"2003","unstructured":"Raman, R., Rao, S.S.: Succinct dynamic dictionaries and trees. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 357\u2013368. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T21:00:38Z","timestamp":1552078838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_38","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}