{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T13:14:16Z","timestamp":1761743656251},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,6,9]],"date-time":"2012-06-09T00:00:00Z","timestamp":1339200000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1007\/s00453-012-9664-0","type":"journal-article","created":{"date-parts":[[2012,6,8]],"date-time":"2012-06-08T16:17:29Z","timestamp":1339172249000},"page":"16-40","source":"Crossref","is-referenced-by-count":40,"title":["A Uniform Paradigm to Succinctly Encode Various Families of Trees"],"prefix":"10.1007","volume":"68","author":[{"given":"Arash","family":"Farzan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,6,9]]},"reference":[{"issue":"1","key":"9664_CR1","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P. Beame","year":"2002","unstructured":"Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci. 65(1), 38\u201372 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9664_CR2","doi-asserted-by":"crossref","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 43(4), 275\u2013292 (2005)","journal-title":"Algorithmica"},{"key":"9664_CR3","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/S0012-365X(99)00054-0","volume":"204","author":"F. Bernhart","year":"1999","unstructured":"Bernhart, F.: Catalan, Motzkin, and Riordan numbers. Discrete Math. 204, 72\u2013112 (1999)","journal-title":"Discrete Math."},{"issue":"5","key":"9664_CR4","doi-asserted-by":"crossref","first-page":"1627","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A. Brodnik","year":"1999","unstructured":"Brodnik, A., Munro, J.I.: Membership in constant time and almost-minimum space. SIAM J. Comput. 28(5), 1627\u20131640 (1999)","journal-title":"SIAM J. Comput."},{"key":"9664_CR5","unstructured":"Clark, D.R.: Compact pat trees. Ph.D. thesis, University of Waterloo, Ontario, Canada (1998)"},{"key":"9664_CR6","first-page":"383","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"D.R. Clark","year":"1996","unstructured":"Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage (extended abstract). In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 383\u2013391 (1996)"},{"issue":"242","key":"9664_CR7","doi-asserted-by":"crossref","first-page":"36","DOI":"10.2307\/3605743","volume":"21","author":"I.M.H. Etherington","year":"1937","unstructured":"Etherington, I.M.H.: Non-associate powers and a functional equation. Math. Gaz. 21(242), 36\u201339 (1937)","journal-title":"Math. Gaz."},{"key":"9664_CR8","unstructured":"Farzan, A.: Succinct representation of trees and graphs. Ph.D. thesis, School of Computer Science, University of Waterloo (2009)"},{"key":"9664_CR9","series-title":"ICALP\u201911","isbn-type":"print","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1007\/978-3-642-22006-7_23","volume-title":"Proceedings of the 38th International Colloquim Conference on Automata, Languages and Programming","author":"A. Farzan","year":"2011","unstructured":"Farzan, A., Kamali, S.: Compact navigation and distance oracles for graphs with small treewidth. In: Proceedings of the 38th International Colloquim Conference on Automata, Languages and Programming, Zurich, Switzerland, ICALP\u201911, vol.\u00a0Part\u00a0I, pp. 268\u2013280. Springer, Berlin (2011). ISBN\u00a0978-3-642-22005-0. http:\/\/dl.acm.org\/citation.cfm?id=2027127.2027156","ISBN":"http:\/\/id.crossref.org\/isbn\/9783642220050"},{"key":"9664_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-540-69903-3_17","volume-title":"SWAT (11th Scandinavian Workshop on Algorithm Theory)","author":"A. Farzan","year":"2008","unstructured":"Farzan, A., Munro, J.I.: A uniform approach towards succinct representation of trees. In: SWAT (11th Scandinavian Workshop on Algorithm Theory). Lecture Notes in Computer Science, pp. 173\u2013184. Springer, Berlin (2008)"},{"key":"9664_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/978-3-642-02927-1_37","volume-title":"International Colloquium on Automata, Languages, and Programming (ICALP) (1)","author":"A. Farzan","year":"2009","unstructured":"Farzan, A., Munro, J.I.: Dynamic succinct ordered trees. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) International Colloquium on Automata, Languages, and Programming (ICALP) (1). Lecture Notes in Computer Science, vol. 5555, pp. 439\u2013450. Springer, Berlin (2009)"},{"key":"9664_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/978-3-642-02927-1_38","volume-title":"ICALP (1)","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.E., Thomas, W. (eds.) ICALP (1). Lecture Notes in Computer Science, vol. 5555, pp. 451\u2013462. Springer, Berlin (2009)"},{"issue":"4","key":"9664_CR13","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14(4), 781\u2013798 (1985)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9664_CR14","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with 0(1) worst case access time. J. ACM 31(3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"issue":"4","key":"9664_CR15","doi-asserted-by":"crossref","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 Trans. Algorithms 2(4), 510\u2013534 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"9664_CR16","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, Boston (1994)"},{"key":"9664_CR17","volume-title":"Graphical Enumeration","author":"F. Harary","year":"1973","unstructured":"Harary, F., Palmer, E.M.: Graphical Enumeration. Academic Press, New York (1973)"},{"key":"9664_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/978-3-540-73420-8_45","volume-title":"International Colloquium on Automata, Languages, and Programming (ICALP)","author":"M. He","year":"2007","unstructured":"He, M., Munro, J.I., Rao, S.S.: Succinct ordinal trees based on tree covering. In: International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 4596, pp. 509\u2013520. Springer, Berlin (2007)"},{"key":"9664_CR19","unstructured":"Jacobson, G.J.: Succinct static data structures. Ph.D. thesis, Pittsburgh, PA, USA (1988)"},{"key":"9664_CR20","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/SFCS.1989.63533","volume-title":"30th Annual Symposium on Foundations of Computer Science","author":"G.J. Jacobson","year":"1989","unstructured":"Jacobson, G.J.: Space-efficient static trees and graphs. In: 30th Annual Symposium on Foundations of Computer Science, pp. 549\u2013554 (1989)"},{"key":"9664_CR21","first-page":"575","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"J. Jansson","year":"2007","unstructured":"Jansson, J., Sadakane, K., Sung, W.-K.: Ultra-succinct representation of ordered trees. In: Bansal, N., Pruhs, K., Stein, C. (eds.) ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 575\u2013584. SIAM, Philadelphia (2007)"},{"key":"9664_CR22","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1997","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. 1, 3rd edn. Addison-Wesley, Reading (1997)","edition":"3"},{"key":"9664_CR23","first-page":"28:1","volume":"4","author":"H.-I. Lu","year":"2008","unstructured":"Lu, H.-I., Yeh, C.-C.: Balanced parentheses strike back. ACM Trans. Algorithms 4, 28:1\u201328:13 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"9664_CR24","first-page":"118","volume-title":"IEEE Symposium on Foundations of Computer Science","author":"J.I. Munro","year":"1997","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)"},{"key":"9664_CR25","first-page":"529","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V., Storm, A.J.: Representing dynamic binary trees succinctly. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 529\u2013536 (2001)"},{"key":"9664_CR26","unstructured":"Odlyzko, A.M.: Some new methods and results in tree enumeration (04 May 1984)"},{"issue":"3","key":"9664_CR27","doi-asserted-by":"crossref","first-page":"583","DOI":"10.2307\/1969046","volume":"49","author":"R. Otter","year":"1948","unstructured":"Otter, R.: The number of trees. Ann. Math., 2nd Ser. 49(3), 583\u2013599 (1948)","journal-title":"Ann. Math., 2nd Ser."},{"issue":"2","key":"9664_CR28","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1137\/S0097539700369909","volume":"31","author":"R. Pagh","year":"2001","unstructured":"Pagh, R.: Low redundancy in static dictionaries with constant query time. SIAM J. Comput. 31(2), 353\u2013363 (2001)","journal-title":"SIAM J. Comput."},{"key":"9664_CR29","first-page":"305","volume-title":"IEEE Annual Symposium on Foundations of Computer Science (FOCS)","author":"M. P\u01cetra\u015fcu","year":"2008","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 305\u2013313. IEEE Comput. Soc., Los Alamitos (2008)"},{"key":"9664_CR30","first-page":"233","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"R. Raman","year":"2002","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233\u2013242 (2002)"},{"issue":"4","key":"9664_CR31","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R. Raman","year":"2007","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9664_CR32","volume-title":"S\u00e9minaire Lotharingien de Combinatoire","author":"G. Rote","year":"1997","unstructured":"Rote, G.: Binary trees having a given number of nodes with 0, 1, and 2 children. In: S\u00e9minaire Lotharingien de Combinatoire, vol. 38. Springer, Berlin (1997)"},{"key":"9664_CR33","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1137\/1.9781611973075.13","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"K. Sadakane","year":"2010","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Charikar, M. (ed.) ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 134\u2013149. SIAM, Philadelphia (2010)"},{"key":"9664_CR34","unstructured":"Storm, A.J.: Representing dynamic binary trees succinctly. Master\u2019s thesis, School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada (2000)"},{"issue":"2","key":"9664_CR35","doi-asserted-by":"crossref","first-page":"121","DOI":"10.2307\/1967710","volume":"24","author":"J.H.M. Wedderburn","year":"1922","unstructured":"Wedderburn, J.H.M.: The functional equation g(x 2)=2ax+[g(x)]2. Ann. Math., 2nd Ser. 24(2), 121\u2013140 (1922)","journal-title":"Ann. Math., 2nd Ser."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9664-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9664-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9664-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:10Z","timestamp":1559137510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9664-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,9]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9664"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9664-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6,9]]}}}