{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:40Z","timestamp":1759637920513},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434009"},{"type":"electronic","value":"9783540459958"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45995-2_44","type":"book-chapter","created":{"date-parts":[[2007,5,29]],"date-time":"2007-05-29T22:33:34Z","timestamp":1180478014000},"page":"508-515","source":"Crossref","is-referenced-by-count":11,"title":["The Level Ancestor Problem Simplified"],"prefix":"10.1007","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[]},{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,14]]},"reference":[{"key":"44_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/3-540-45022-X_8","volume-title":"Improved algorithms for finding level-ancestors in dynamic trees","author":"S. Alstrup","year":"2000","unstructured":"S. Alstrup and J. Holm. Improved algorithms for finding level-ancestors in dynamic trees. In 27th International Colloquium on Automata, Languages and Programming (ICALP\u2019 00), LNCS. 1853, pages 73\u201384, 2000."},{"key":"44_CR2","doi-asserted-by":"crossref","unstructured":"M. A. Bender, E. Demaine, and M. Farach-Colton. Cache-oblivious B-trees. In 41st Annual Symposium on Foundations of Computer Science (FOCS), pages 399\u2013409, 2000.","DOI":"10.1109\/SFCS.2000.892128"},{"key":"44_CR3","first-page":"88","volume-title":"Lecture Notes in Computer Science","author":"Michael A. Bender","year":"2000","unstructured":"M. A. Bender and M. Farach-Colton. The LCA problem revisited. In LATIN, pages 88\u201394, 2000."},{"key":"44_CR4","doi-asserted-by":"crossref","unstructured":"O. Berkman and U. Vishkin. Recursive *-tree parallel data-structure. In Proc. of the 30th IEEE Annual Symp. on Foundation of Computer Science, pages 196\u2013202, 1989.","DOI":"10.1109\/SFCS.1989.63478"},{"issue":"2","key":"44_CR5","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O. Berkman","year":"1993","unstructured":"O. Berkman and U. Vishkin. Recursive star-tree parallel data structure. SIAM J. Comput., 22(2):221\u2013242, Apr. 1993.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"44_CR6","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O. Berkman","year":"1994","unstructured":"O. Berkman and U. Vishkin. Finding level-ancestors in trees. J. Comput. Syst. Sci., 48(2):214\u2013230, Apr. 1994.","journal-title":"J. Comput. Syst. Sci."},{"key":"44_CR7","unstructured":"R. Cole and R. Hariharan. Dynamic LCA queries on trees. In Proc. of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 235\u2013244, 1999."},{"key":"44_CR8","doi-asserted-by":"crossref","unstructured":"P. F. Dietz. Finding level-ancestors in dynamic trees. In Workshop on Algorithms and Data Structures, pages 32\u201340, 1991.","DOI":"10.1007\/BFb0028247"},{"key":"44_CR9","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, J. L. Bentley, and R. E. Tarjan. Scaling and related techniques for geometry problems. In Proc. of the 16th Ann. ACM Symp. on Theory of Computing, pages 135\u2013143, 1984.","DOI":"10.1145\/800057.808675"},{"issue":"2","key":"44_CR10","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338\u2013355, 1984.","journal-title":"SIAM J. Comput."},{"key":"44_CR11","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin. On finding lowest common ancestors: Simplification and parallelization. SIAM J. Comput., 17:1253\u20131262, 1988.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"44_CR12","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"R. E. Tarjan","year":"1979","unstructured":"R. E. Tarjan. Applications of path compression on balanced trees. Journal of the ACM, 26(4):690\u2013715, Oct. 1979.","journal-title":"Journal of the ACM"},{"key":"44_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0255(99)00046-8","volume":"119","author":"B. Wang","year":"1999","unstructured":"B. Wang, J. Tsai, and Y. Chuang. The lowest common ancestor problem on a tree with unfixed root. Information Sciences, 119:125\u2013130, 1999.","journal-title":"Information Sciences"},{"issue":"1","key":"44_CR14","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0020-0190(94)00058-1","volume":"51","author":"Z. Wen","year":"1994","unstructured":"Z. Wen. New algorithms for the LCA problem and the binary tree reconstruction problem. Inf. Process. Lett., 51(1):11\u201316, 1994.","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","LATIN 2002: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45995-2_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,20]],"date-time":"2019-02-20T10:55:05Z","timestamp":1550660105000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45995-2_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434009","9783540459958"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45995-2_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2002]]}}}