{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:57:56Z","timestamp":1725537476923},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"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-04128-0_67","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"752-763","source":"Crossref","is-referenced-by-count":3,"title":["Short Labels for Lowest Common Ancestors in Trees"],"prefix":"10.1007","author":[{"given":"Johannes","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"67_CR1","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S. Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math.\u00a05(4), 596\u2013603 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"67_CR2","doi-asserted-by":"publisher","first-page":"1295","DOI":"10.1137\/S0097539703437211","volume":"35","author":"S. Abiteboul","year":"2006","unstructured":"Abiteboul, S., Alstrup, S., Kaplan, H., Milo, T., Rauhe, T.: Compact labeling scheme for ancestor queries. SIAM J. Comput.\u00a035(6), 1295\u20131309 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"67_CR3","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s00224-005-1281-8","volume":"40","author":"H. Kaplan","year":"2007","unstructured":"Kaplan, H., Milo, T., Shabo, R.: Compact labeling scheme for xml ancestor queries. Theory Comput. Syst.\u00a040(1), 55\u201399 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"67_CR4","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/S0895480103433409","volume":"19","author":"S. Alstrup","year":"2005","unstructured":"Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. SIAM J. Discrete Math.\u00a019(2), 448\u2013462 (2005)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"67_CR5","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C. Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms\u00a053(1), 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"issue":"5","key":"67_CR6","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E. Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput.\u00a032(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"67_CR7","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."},{"key":"67_CR8","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s00224-004-1155-5","volume":"37","author":"S. Alstrup","year":"2004","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: A survey and a new algorithm for a distributed environment. Theory Comput. Syst.\u00a037, 441\u2013456 (2004)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"67_CR9","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1016\/j.tcs.2005.03.015","volume":"340","author":"D. Peleg","year":"2005","unstructured":"Peleg, D.: Informative labeling schemes for graphs. Theor. Comput. Sci.\u00a0340(3), 577\u2013593 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"67_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-540-87744-8_20","volume-title":"Algorithms - ESA 2008","author":"S. Caminiti","year":"2008","unstructured":"Caminiti, S., Finocchi, I., Petreschi, R.: Engineering tree labeling schemes: A case study on least common ancestors. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 234\u2013245. Springer, Heidelberg (2008)"},{"issue":"1","key":"67_CR11","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"372","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theor. Comput. Sci.\u00a0372(1), 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"67_CR12","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1002\/j.1538-7305.1959.tb01583.x","volume":"38","author":"E.N. Gilbert","year":"1959","unstructured":"Gilbert, E.N., Moore, E.F.: Variable length binary encodings. Bell System Tech. J.\u00a038, 933\u2013968 (1959)","journal-title":"Bell System Tech. J."},{"key":"67_CR13","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/0121057","volume":"21","author":"T.C. Hu","year":"1971","unstructured":"Hu, T.C., Tucker, A.C.: Optimum computer search trees. SIAM J. Appl. Math.\u00a021, 514\u2013532 (1971)","journal-title":"SIAM J. Appl. Math."},{"key":"67_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11561071_22","volume-title":"Algorithms \u2013 ESA 2005","author":"T.C. Hu","year":"2005","unstructured":"Hu, T.C., Larmore, L.L., Morgenthaler, J.D.: Optimal integer alphabetic trees in linear time. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 226\u2013237. Springer, Heidelberg (2005)"},{"issue":"2","key":"67_CR15","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/0206017","volume":"6","author":"K. Mehlhorn","year":"1977","unstructured":"Mehlhorn, K.: The best possible bound for the weighted path length of binary search trees. SIAM J. Comput.\u00a06(2), 235\u2013239 (1977)","journal-title":"SIAM J. Comput."},{"key":"67_CR16","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/BF00264289","volume":"1","author":"D.E. Knuth","year":"1971","unstructured":"Knuth, D.E.: Optimum binary search trees. Act Informatica\u00a01, 14\u201325 (1971)","journal-title":"Act Informatica"},{"key":"67_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"J.I. Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"67_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-3-642-02011-7_16","volume-title":"SEA 2009","author":"S. Gog","year":"2009","unstructured":"Gog, S.: Broadword computing and Fibonacci code speed up compressed suffix arrays. In: Gog, S., Vahrenhold, J. (eds.) SEA 2009. LNCS, vol.\u00a05526, pp. 161\u2013172. Springer, Heidelberg (2009)"},{"key":"67_CR19","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"I.H. Witten","year":"1999","unstructured":"Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd edn. Morgan Kaufmann, San Francisco (1999)","edition":"2"},{"issue":"4","key":"67_CR20","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1137\/0206045","volume":"6","author":"A.M. Garsia","year":"1977","unstructured":"Garsia, A.M., Wachs, M.L.: A new algorithm for minimum cost binary trees. SIAM J. Comput.\u00a06(4), 622\u2013642 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"67_CR21","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1051\/ita\/1985190201791","volume":"19","author":"J.L. R\u00e9my","year":"1985","unstructured":"R\u00e9my, J.L.: Un proc\u00e9d\u00e9 it\u00e9ratif de d\u00e9nombrement d\u2019arbres binaires et son application a leur g\u00e9n\u00e9ration al\u00e9atoire. Informatique Th\u00e9orique et Applications\u00a019(2), 179\u2013195 (1985)","journal-title":"Informatique Th\u00e9orique et Applications"},{"key":"67_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/11780441_5","volume-title":"Combinatorial Pattern Matching","author":"J. Fischer","year":"2006","unstructured":"Fischer, J., Heun, V.: Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 36\u201348. Springer, Heidelberg (2006)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_67","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T08:45:14Z","timestamp":1548405914000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}