{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T15:52:58Z","timestamp":1773330778433,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,2,5]],"date-time":"2015-02-05T00:00:00Z","timestamp":1423094400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00453-015-9969-x","type":"journal-article","created":{"date-parts":[[2015,2,4]],"date-time":"2015-02-04T09:14:24Z","timestamp":1423041264000},"page":"742-777","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Succinct Dynamic Cardinal Trees"],"prefix":"10.1007","volume":"74","author":[{"given":"Diego","family":"Arroyuelo","sequence":"first","affiliation":[]},{"given":"Pooya","family":"Davoodi","sequence":"additional","affiliation":[]},{"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,5]]},"reference":[{"key":"9969_CR1","doi-asserted-by":"crossref","unstructured":"Apostolico, A.: The myriad virtues of subword trees. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words. NATO ISI Series, pp. 85\u201396. Springer, Berlin (1985)","DOI":"10.1007\/978-3-642-82456-2_6"},{"key":"9969_CR2","doi-asserted-by":"crossref","unstructured":"Arroyuelo, D.: An improved succinct representation for dynamic k-ary trees. In: Proceedings of 19th Annual Symposium on Combinatorial Pattern Matching (CPM), vol. 5029 of Lecture Notes in Computer Science, pp. 277\u2013289. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-69068-9_26"},{"key":"9969_CR3","doi-asserted-by":"crossref","unstructured":"Arroyuelo D., C\u00e1novas, R., Navarro, G., Sadakane, K.: Succinct trees in practice. In: Proceedings of 11th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 84\u201397. SIAM (2010)","DOI":"10.1137\/1.9781611972900.9"},{"issue":"7","key":"9969_CR4","doi-asserted-by":"crossref","first-page":"1070","DOI":"10.1016\/j.ic.2011.03.001","volume":"209","author":"D Arroyuelo","year":"2011","unstructured":"Arroyuelo, D., Navarro, G.: Space-efficient construction of Lempel\u2013Ziv compressed text indexes. Inf. Comput. 209(7), 1070\u20131102 (2011)","journal-title":"Inf. Comput."},{"issue":"1","key":"9969_CR5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"M Bender","year":"2004","unstructured":"Bender, M., Farach-Colton, M.: The level ancestor problem simplified. Theor. Comput. Sci. 321(1), 5\u201312 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9969_CR6","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"M Bender","year":"2005","unstructured":"Bender, M., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms 57(2), 75\u201394 (2005)","journal-title":"J. Algorithms"},{"issue":"4","key":"9969_CR7","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., 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":"9969_CR8","doi-asserted-by":"crossref","unstructured":"Brodnik, A., Carlsson, S., Demaine, E., Munro, J.I., Sedgewick, R.: Resizable arrays in optimal time and space. In: Proceedings of 6th International Workshop on Algorithms and Data Structures (WADS), vol. 1663 of Lecture Notes in Computer Science, pp. 37\u201348. Springer (1999)","DOI":"10.1007\/3-540-48447-7_4"},{"key":"9969_CR9","doi-asserted-by":"crossref","unstructured":"Chan, H.-L., Hon, W.-K., Lam, T.-W., Sadakane, K.: Compressed indexes for dynamic text collections. ACM Trans. Algorithms 3(2), article 21 (2007)","DOI":"10.1145\/1240233.1240244"},{"key":"9969_CR10","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"3","key":"9969_CR11","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/spe.4380230305","volume":"23","author":"J Darragh","year":"1993","unstructured":"Darragh, J., Cleary, J., Witten, I.: Bonsai: a compact representation of trees. Softw. Pract. Exp. 23(3), 277\u2013291 (1993)","journal-title":"Softw. Pract. Exp."},{"key":"9969_CR12","doi-asserted-by":"crossref","unstructured":"Davoodi, P., Rao, S.S.: Succinct dynamic cardinal trees with constant time operations for small alphabet. In: Proceedings of 8th Annual Conference on Theory and Applications of Models of Computation (TAMC), vol. 6648 of Lecture Notes in Computer Science, pp. 195\u2013205. Springer (2011)","DOI":"10.1007\/978-3-642-20877-5_21"},{"key":"9969_CR13","doi-asserted-by":"crossref","first-page":"2668","DOI":"10.1016\/j.tcs.2010.10.030","volume":"412","author":"A Farzan","year":"2011","unstructured":"Farzan, A., Munro, J.I.: Succinct representation of dynamic trees. Theor. Comput. Sci. 412, 2668\u20132678 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9969_CR14","doi-asserted-by":"crossref","unstructured":"Farzan, A., Raman, R., Rao, S.S.: Universal succinct representations of trees? In: Proceedings of 36th International Colloquium on Automata, Languages and Programming (ICALP), vol. 5555 of Lecture Notes in Computer Science, pp. 451\u2013462. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_38"},{"key":"9969_CR15","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. J. ACM 57(1), Article 4 (2009)","DOI":"10.1145\/1613676.1613680"},{"key":"9969_CR16","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms 3(2), article 20 (2007)","DOI":"10.1145\/1240233.1240243"},{"issue":"1","key":"9969_CR17","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1145\/322290.322305","volume":"29","author":"ML Fredman","year":"1982","unstructured":"Fredman, M.L.: The complexity of maintaining an array and computing its partial sums. J. ACM 29(1), 250\u2013260 (1982)","journal-title":"J. ACM"},{"issue":"4","key":"9969_CR18","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1145\/1198513.1198516","volume":"2","author":"R Geary","year":"2006","unstructured":"Geary, R., 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":"9969_CR19","volume-title":"Concrete Mathematics\u2014a Foundation for Computer Science","author":"RL Graham","year":"1994","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics\u2014a Foundation for Computer Science, 2nd edn. Addison-Wesley, Reading (1994)","edition":"2"},{"issue":"39","key":"9969_CR20","doi-asserted-by":"crossref","first-page":"5176","DOI":"10.1016\/j.tcs.2011.05.023","volume":"412","author":"W-K Hon","year":"2011","unstructured":"Hon, W.-K., Sadakane, K., Sung, W.-K.: Succinct data structures for searchable partial sums with optimal worst-case performance. Theor. Comput. Sci. 412(39), 5176\u20135186 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9969_CR21","doi-asserted-by":"crossref","unstructured":"Jacobson, G. Space-efficient static trees and graphs. In: Proceedings of 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 549\u2013554. IEEE Computer Society (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"9969_CR22","doi-asserted-by":"crossref","unstructured":"Jansson, J., Sadakane, K., Sung, W.-K.: Linked dynamic tries with applications to LZ-compression in sublinear time and space. Algorithmica (2013). doi: 10.1007\/s00453-013-9836-6","DOI":"10.1007\/s00453-013-9836-6"},{"issue":"2","key":"9969_CR23","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/j.jcss.2011.09.002","volume":"78","author":"J Jansson","year":"2012","unstructured":"Jansson, J., Sadakane, K., Sung, W.-K.: Ultra-succinct representation of ordered trees with applications. J. Comput. Syst. Sci. 78(2), 619\u2013631 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9969_CR24","doi-asserted-by":"crossref","unstructured":"Joannou, S., Raman, R.: Dynamizing succinct tree representations. In: Proceedings of 11th International Symposium on Experimental Algorithms (SEA), vol. 7276 of Lecture Notes in Computer Science, pp. 224\u2013235. Springer (2012)","DOI":"10.1007\/978-3-642-30850-5_20"},{"key":"9969_CR25","doi-asserted-by":"crossref","unstructured":"Lu, H.-I., Yeh, C.-C.: Balanced parentheses strike back. ACM Trans. Algorithms 4(3), 28:1\u201328:13 (2008)","DOI":"10.1145\/1367064.1367068"},{"issue":"3","key":"9969_CR26","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows\u2013Wheeler transform. J. ACM 48(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"issue":"3","key":"9969_CR27","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"key":"9969_CR28","unstructured":"Munro, J.I., Raman, V., Storm, A.J.: Representing dynamic binary trees succinctly. In: Proceedings of 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 529\u2013536. ACM\/SIAM (2001)"},{"issue":"5","key":"9969_CR29","doi-asserted-by":"crossref","first-page":"1781","DOI":"10.1137\/130908245","volume":"43","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. SIAM J. Comput. 43(5), 1781\u20131806 (2014)","journal-title":"SIAM J. Comput."},{"key":"9969_CR30","doi-asserted-by":"crossref","unstructured":"Navarro, G., Sadakane, K.: Fully-functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), article 16 (2014)","DOI":"10.1145\/2601073"},{"key":"9969_CR31","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct dynamic data structures. In: Proceedings of 7th International Workshop on Algorithms and Data Structures (WADS), vol. 2125 of Lecture Notes in Computer Science, pp. 426\u2013437. Springer (2001)","DOI":"10.1007\/3-540-44634-6_39"},{"key":"9969_CR32","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), Article 43 (2009)","DOI":"10.1145\/1290672.1290680"},{"key":"9969_CR33","doi-asserted-by":"crossref","unstructured":"Raman, R., Rao, S.S.: Succinct dynamic dictionaries and trees. In: Proceedings of 30th International Colloquium on Automata, Languages and Programming (ICALP), vol. 2719 of Leture Notes in Computer Science, pp. 357\u2013368. Springer (2003)","DOI":"10.1007\/3-540-45061-0_30"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9969-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9969-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9969-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T12:29:35Z","timestamp":1566304175000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9969-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,5]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9969"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9969-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,5]]}}}