{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:40Z","timestamp":1725664720635},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_133","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:36:48Z","timestamp":1330292208000},"page":"212-222","source":"Crossref","is-referenced-by-count":1,"title":["Optimal pointer algorithms for finding nearest common ancestors in dynamic trees"],"prefix":"10.1007","author":[{"given":"Stephen","family":"Alstrup","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"19_CR1","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974."},{"issue":"1","key":"19_CR2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1137\/0205011","volume":"5","author":"A.V. Aho","year":"1976","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. On finding lowest common ancestor in trees. SIAM Journal on computing, 5(1):115\u2013132, 1976. See also STOC 1973.","journal-title":"SIAM Journal on computing"},{"key":"19_CR3","unstructured":"S. Alstrup. Optimal algorithms for finding nearest common ancestors in dynamic trees. Technical Report 95-30, Department of Computer Science, University of Copenhagen, 1995."},{"key":"19_CR4","first-page":"434","volume":"1","author":"H.N. Gabow","year":"1990","unstructured":"H.N. Gabow. Data structure for weighted matching and nearest common ancestors with linking. In Annual ACM-SIAM Symposium on discrete algorithms (SODA), volume 1, pages 434\u2013443, 1990.","journal-title":"Annual ACM-SIAM Symposium on discrete algorithms (SODA)"},{"issue":"2","key":"19_CR5","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H.N. Gabow","year":"1985","unstructured":"H.N. Gabow and R.E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of computer and system sciences, 30(2):209\u2013221, 1985.","journal-title":"Journal of computer and system sciences"},{"issue":"2","key":"19_CR6","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"},{"issue":"3","key":"19_CR7","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"D.D. Sleator and R.E. Tarjan. A data structure for dynamic trees. Journal of computer and system sciences, 26(3):362\u2013391, 1983. See also STOC 1981.","journal-title":"Journal of computer and system sciences"},{"issue":"4","key":"19_CR8","doi-asserted-by":"crossref","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 association for computing machinery (J.ACM), 26(4):690\u2013715, 1979.","journal-title":"Journal of the association for computing machinery (J.ACM)"},{"issue":"2","key":"19_CR9","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R.E. Tarjan","year":"1979","unstructured":"R.E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of computer and system sciences, 18(2):110\u2013127, 1979.","journal-title":"Journal of computer and system sciences"},{"key":"19_CR10","unstructured":"A. K. Tsakalides and J. van Leeuwen. An optimal pointer machine algorithm for finding nearest common ansectors. Technical Report RUU-CS-88-17, Department of Computer Science, University of Utrecht, 1988."},{"issue":"1","key":"19_CR11","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF00268844","volume":"25","author":"A.K. Tsakalidis","year":"1988","unstructured":"A.K. Tsakalidis. The nearest common ancestor in a dynamic tree. Acta informatica, 25(1):37\u201354, 1988.","journal-title":"Acta informatica"},{"key":"19_CR12","unstructured":"J. van Leeuwen. Finding lowest common ancestors in less than logarithmic time. Unpublish technical report, 1976."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_133.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:31:53Z","timestamp":1619573513000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_133","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}