{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T08:53:36Z","timestamp":1673168016181},"reference-count":25,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3643,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,9]]},"DOI":"10.1016\/s0022-0000(03)00013-8","type":"journal-article","created":{"date-parts":[[2003,5,13]],"date-time":"2003-05-13T01:09:12Z","timestamp":1052788152000},"page":"381-418","source":"Crossref","is-referenced-by-count":11,"title":["Optimal finger search trees in the pointer machine"],"prefix":"10.1016","volume":"67","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Lagogiannis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Makris","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Athanasios","family":"Tsakalidis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kostas","family":"Tsichlas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(03)00013-8_BIB1","unstructured":"G.M. Adel'son-Vel'skii, E.M. Landis, An algorithm for the organization and information, Dokl. Acad. Nauk SSSR 146 263\u2013266 (in Russian) (English Translation in Soviet Math. 3 (1962) 1259\u20131262.)."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB2","doi-asserted-by":"crossref","unstructured":"A. Anderson, M. Thorup, Tight(er) worst-case bounds on dynamic searching and priority queues, in: Proceedings of the 32nd Annual ACM Symposium On Theory of Computing (STOC), ACM, 2000, pp. 335\u2013342.","DOI":"10.1145\/335305.335344"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB3","doi-asserted-by":"crossref","unstructured":"M.J. Atallah, M. Goodrich, K. Ramaiyer, Biased finger trees and three-dimensional layers of maxima, in: Proceedings of the 10th ACM Symposium on Computational Geometry, 1994, pp. 150\u2013159.","DOI":"10.1145\/177424.177601"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB4","series-title":"Pointer machines and pointer algorithms: an annotated bibliography, Technical Report D-351","author":"Ben-Amram","year":"1998"},{"issue":"3","key":"10.1016\/S0022-0000(03)00013-8_BIB5","first-page":"238","article-title":"Partially persistent data structures of bounded degree with constant update time","volume":"3","author":"Brodal","year":"1996","journal-title":"Nordic J. Comput."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB6","unstructured":"G.S. Brodal, Finger search trees with constant insertion time, in: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998, pp. 540\u2013549."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB7","series-title":"A programming and problem-solving seminar, Technical Report STAN-CS-77-606","author":"Clancy","year":"1977"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB8","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(94)00115-4","article-title":"A constant update time finger search tree","volume":"52","author":"Dietz","year":"1994","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB9","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","article-title":"Making data structures persistent","volume":"38","author":"Driscoll","year":"1989","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB10","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1142\/S0129054196000117","article-title":"A simple balanced search tree with O(1) worst-case update time","volume":"7","author":"Fleischer","year":"1996","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB11","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","article-title":"Linear time algorithms for visibility and shortest path problems inside simple polygons","volume":"2","author":"Guibas","year":"1987","journal-title":"Algorithmica"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB12","doi-asserted-by":"crossref","unstructured":"L.J. Guibas, E.M. McCreight, M.P. Plass, J.R. Roberts, A new representation for linear lists, in: Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC), ACM, 1977, pp. 49\u201360.","DOI":"10.1145\/800105.803395"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB13","series-title":"Fast updates with a guaranteed time bound per update, Techincal Report 154","author":"Harel","year":"1980"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB14","series-title":"A data structure with movable fingers and deletions, Technical Report 145","author":"Harel","year":"1979"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB15","doi-asserted-by":"crossref","unstructured":"J. Hershberger, Finding the visibility graph of a simple polygon in time proportional to its size, in: Proceedings of the Third ACM Symposium on Computational Geometry, 1987, pp. 11\u201320.","DOI":"10.1145\/41958.41960"},{"issue":"1\u20133","key":"10.1016\/S0022-0000(03)00013-8_BIB16","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/S0019-9958(86)80033-X","article-title":"Sorting Jordan sequences in linear time using level-linked search trees","volume":"68","author":"Hoffman","year":"1986","journal-title":"Inform. Control"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB17","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00288968","article-title":"A new data structure for representing sorted lists","volume":"17","author":"Huddleston","year":"1982","journal-title":"Acta Inform."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB18","doi-asserted-by":"crossref","unstructured":"S.R. Kosaraju, Localized search in sorted lists, in: Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC), ACM, 1981, pp. 62\u201369.","DOI":"10.1145\/800076.802458"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB19","unstructured":"G. Lagogiannis, C. Makris, Y. Panagis, K. Tsichlas, New dynamic balanced search trees with worst-case constant update time, in: Proceedings of the 13th Australasian Workshop on Combinatorial Algorithms (AWOCA 2002), 2002."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB20","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF00299635","article-title":"A balanced search tree with O(1) worst-case update time","volume":"26","author":"Levcopoulos","year":"1988","journal-title":"Acta Inform."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB21","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, A. Tsakalidis, Handbook of Theoretical Computer Science\u2014Vol. I: Algorithms and Complexity, Data Structures, The MIT Press, 1990, pp. 303\u2013341 (Chapter 6).","DOI":"10.1016\/B978-0-444-88071-0.50011-4"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB22","first-page":"27","article-title":"An O(1) average time update scheme for balanced search trees","volume":"18","author":"Overmars","year":"1982","journal-title":"Bull. EATCS"},{"key":"10.1016\/S0022-0000(03)00013-8_BIB23","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","article-title":"A class of algorithms which require nonlinear time to maintain disjoint sets","volume":"18","author":"Tarjan","year":"1979","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB24","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0020-0190(83)90099-6","article-title":"Updating a balanced search tree in O(1) rotations","volume":"16","author":"Tarjan","year":"1983","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0022-0000(03)00013-8_BIB25","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0019-9958(85)80034-6","article-title":"AVL-trees for localized search","volume":"67","author":"Tsakalidis","year":"1985","journal-title":"Inform. Control"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000138?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000138?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T21:47:45Z","timestamp":1584654465000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,9]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,9]]}},"alternative-id":["S0022000003000138"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00013-8","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,9]]}}}