{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:40:03Z","timestamp":1748461203898,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476659"},{"type":"electronic","value":"9783662476666"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_45","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T07:46:47Z","timestamp":1434700007000},"page":"564-574","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Simple and Optimal Ancestry Labeling Scheme for Trees"],"prefix":"10.1007","author":[{"given":"S\u00f8ren","family":"Dahlgaard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathias B\u00e6k Tejs","family":"Knudsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noy","family":"Rotbart","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"6","key":"45_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 scheme for ancestor queries. SIAM J. Comput. 35(6), 1295\u20131309 (2006)","journal-title":"SIAM J. Comput."},{"key":"45_CR2","unstructured":"Abiteboul, S., Buneman, P., Suciu, D.: Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann (1999)"},{"key":"45_CR3","unstructured":"Abiteboul, S., Kaplan, H., Milo, T.: Compact labeling schemes for ancestor queries. In: Proc. 25th ACM-SIAM Symposium on Discrete Algorithms, pp. 547\u2013556 (2001)"},{"issue":"2","key":"45_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. Discret. Math. 19(2), 448\u2013462 (2005)","journal-title":"SIAM J. Discret. Math."},{"key":"45_CR5","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: A survey and a new distributed algorithm. pp. 258\u2013264. ACM Press (2002)","DOI":"10.1145\/564870.564914"},{"key":"45_CR6","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Halvorsen, E.B., Larsen, K.G.: Near-optimal labeling schemes for nearest common ancestors. In: SODA, pp. 972\u2013982 (2014)","DOI":"10.1137\/1.9781611973402.72"},{"key":"45_CR7","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Kaplan, H., Thorup, M., Zwick, U.: Adjacency labeling schemes and induced-universal graphs. CoRR, abs\/1404.3391 (2014) (to appear in STOC 2015)","DOI":"10.1145\/2746539.2746545"},{"key":"45_CR8","unstructured":"Alstrup, S., Rauhe, T.: Improved labeling scheme for ancestor queries. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp, 947\u2013953 (2002)"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Rauhe, T.: Small induced-universal graphs and compact implicit graph representations. In: FOCS 2002, pp. 53\u201362 (2002)","DOI":"10.1109\/SFCS.2002.1181882"},{"issue":"5","key":"45_CR10","doi-asserted-by":"publisher","first-page":"2048","DOI":"10.1137\/070687633","volume":"39","author":"E Cohen","year":"2010","unstructured":"Cohen, E., Kaplan, H., Milo, T.: Labeling dynamic xml trees. SIAM Journal on Computing 39(5), 2048\u20132074 (2010)","journal-title":"SIAM Journal on Computing"},{"issue":"11\u201316","key":"45_CR11","doi-asserted-by":"publisher","first-page":"1155","DOI":"10.1016\/S1389-1286(99)00020-1","volume":"31","author":"A Deutsch","year":"1999","unstructured":"Deutsch, A., Fern\u00e1ndez, M.F., Florescu, D., Levy, A.Y., Suciu, D.: A query language for XML. Computer Networks 31(11\u201316), 1155\u20131169 (1999)","journal-title":"Computer Networks"},{"key":"45_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/3-540-48224-5_62","volume-title":"Automata, Languages and Programming","author":"P Fraigniaud","year":"2001","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in Trees. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 757\u2013772. Springer, Heidelberg (2001)"},{"key":"45_CR13","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A.: Compact ancestry labeling schemes for xml trees. In: Proc. 21st ACM-SIAM Symp. on Discrete Algorithms (SODA) (2010)","DOI":"10.1137\/1.9781611973075.38"},{"key":"45_CR14","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A.: An optimal ancestry scheme and small universal posets. In: STOC 2010, pp. 611\u2013620 (2010)","DOI":"10.1145\/1806689.1806773"},{"key":"45_CR15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoillea","year":"2004","unstructured":"Gavoillea, C., Peleg, D., P\u00e9rennesc, S., Razb, R.: Distance labeling in graphs. Journal of Algorithms 53, 85\u2013112 (2004)","journal-title":"Journal of Algorithms"},{"key":"45_CR16","doi-asserted-by":"crossref","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 334\u2013343 (1992)","DOI":"10.1137\/0405049"},{"key":"45_CR17","doi-asserted-by":"crossref","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM Journal on Computing 34(1), 23\u201340 (2004)","DOI":"10.1137\/S0097539703433912"},{"key":"45_CR18","doi-asserted-by":"crossref","unstructured":"Korman, A.: Labeling schemes for vertex connectivity. ACM Transactions on Algorithms 6(2) (2010)","DOI":"10.1145\/1721837.1721855"},{"issue":"1","key":"45_CR19","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1137\/0203006","volume":"3","author":"Robert Endre Tarjan","year":"1974","unstructured":"Robert Endre Tarjan: Finding dominators in directed graphs. SIAM J. Comput. 3(1), 62\u201389 (1974)","journal-title":"SIAM J. Comput."},{"key":"45_CR20","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA 2001, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:02:58Z","timestamp":1748458978000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}