{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T18:11:56Z","timestamp":1742926316974,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540877431"},{"type":"electronic","value":"9783540877448"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87744-8_20","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T09:20:52Z","timestamp":1220088052000},"page":"234-245","source":"Crossref","is-referenced-by-count":6,"title":["Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors"],"prefix":"10.1007","author":[{"given":"Saverio","family":"Caminiti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irene","family":"Finocchi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rossella","family":"Petreschi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"20_CR1","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 schemes for ancestor queries. SIAM J. on Computing\u00a035(6), 1295\u20131309 (2006)","journal-title":"SIAM J. on Computing"},{"issue":"2","key":"20_CR2","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. on Discrete Mathematics\u00a019(2), 448\u2013462 (2005)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: a survey and a new distributed algorithm. In: Proc. ACM SPAA 2002, pp. 258\u2013264 (2002)","DOI":"10.1145\/564870.564914"},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/11780823_12","volume-title":"Structural Information and Communication Complexity","author":"N. Bonichon","year":"2006","unstructured":"Bonichon, N., Gavoille, C., Labourel, A.: Short labels by traversal and jumping. In: Flocchini, P., G\u0105sieniec, L. (eds.) SIROCCO 2006. LNCS, vol.\u00a04056, pp. 143\u2013156. Springer, Heidelberg (2006)"},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/TIT.1966.1053860","volume":"IT-12","author":"M.A. Breuer","year":"1966","unstructured":"Breuer, M.A.: Coding the vertexes of a graph. IEEE Transactions on Information Theory\u00a0IT-12, 148\u2013153 (1966)","journal-title":"IEEE Transactions on Information Theory"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/0022-247X(67)90082-0","volume":"20","author":"M.A. Breuer","year":"1967","unstructured":"Breuer, M.A., Folkman, J.: An unexpected result on coding the vertices of a graph. J. of Mathematical Analysis and Applications\u00a020, 583\u2013600 (1967)","journal-title":"J. of Mathematical Analysis and Applications"},{"key":"20_CR7","unstructured":"Caminiti, S., Finocchi, I., Petreschi, R.: Concurrent data structures for lowest common ancestors (manuscript, 2008)"},{"issue":"2","key":"20_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.tcs.2007.03.009","volume":"382","author":"S. Caminiti","year":"2007","unstructured":"Caminiti, S., Finocchi, I., Petreschi, R.: On coding labeled trees. Theoretical Computer Science\u00a0382(2), 97\u2013108 (2007)","journal-title":"Theoretical Computer Science"},{"key":"20_CR9","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and Distance Queries via 2-hop Labels. In: Proc. ACM-SIAM SODA 2002, pp. 937\u2013946 (2002)"},{"issue":"4","key":"20_CR10","doi-asserted-by":"publisher","first-page":"894","DOI":"10.1137\/S0097539700370539","volume":"34","author":"R. Cole","year":"2005","unstructured":"Cole, R., Hariharan, R.: Dynamic LCA Queries on Trees. SIAM J. on Computing\u00a034(4), 894\u2013923 (2005)","journal-title":"SIAM J. on Computing"},{"key":"20_CR11","unstructured":"Gavoille, C., Peleg, D., Perennes, S., Raz, R.: Distance labeling in graphs. In: Proc. ACM-SIAM SODA 2001, pp. 210\u2013219 (2001)"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. In: Proc. ACM STOC 1988, pp. 334\u2013343 (1988)","DOI":"10.1145\/62212.62244"},{"key":"20_CR13","unstructured":"Kaplan, H., Milo, T., Shabo, R.: A Comparison of Labeling Schemes for Ancestor Queries. In: Proc. ACM-SIAM SODA 2002, pp. 954\u2013963 (2002)"},{"issue":"1","key":"20_CR14","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M. Katz","year":"2004","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. on Computing\u00a034(1), 23\u201340 (2004)","journal-title":"SIAM J. on Computing"},{"key":"20_CR15","unstructured":"Kopelowitz, T., Lewenstein, M.: Dynamic weighted ancestors. In: Proc. ACM-SIAM SODA 2007, pp. 565\u2013574 (2007)"},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/3-540-46784-X_5","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Peleg","year":"1999","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, pp. 30\u201341. Springer, Heidelberg (1999)"},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/3-540-44612-5_53","volume-title":"Mathematical Foundations of Computer Science 2000","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Informative labeling schemes for graphs. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol.\u00a01893, pp. 579\u2013588. Springer, Heidelberg (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2008"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87744-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T05:15:56Z","timestamp":1715058956000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87744-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540877431","9783540877448"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87744-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}