{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:24:25Z","timestamp":1787509465467,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540614227","type":"print"},{"value":"9783540685296","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_132","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:36:49Z","timestamp":1330274209000},"page":"198-211","source":"Crossref","is-referenced-by-count":6,"title":["Lower bounds for dynamic transitive closure, planar point location, and parentheses matching"],"prefix":"10.1007","author":[{"given":"Thore","family":"Husfeldt","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Theis","family":"Rauhe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u00f8ren","family":"Skyum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Arne Andersson. Sublogarithmic searching without multiplications. In Proc. 36th FOCS, pages 655\u2013663. IEEE Computer Society, 1995.","DOI":"10.1109\/SFCS.1995.492667"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Arne Andersson, Torben Hagerup, Stefan Nilsson, and Rajeev Raman. Sorting in linear time? In Proc 27thSTOC, pages 427\u2013436, 1995.","DOI":"10.1145\/225058.225173"},{"key":"18_CR3","unstructured":"Paul Beame and Faith Fich, 1994. Personal communication, reported by Peter Bro Miltersen."},{"key":"18_CR4","unstructured":"Yi-Jen Chiang and Roberto Tamassia. Dynamic algorithms in Computational Geometry. Technical Report CS-91-24, Dept. of Comp. Sc., Brown University, 1991."},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and loannis G. Tollis. Algorithms for drawing graphs: an annotated bibliography. Available via anonymous ftp from wilma.cs.brown.edu in \/pub\/papers\/compgeo\/gdbiblio.ps.Z, 1994.","DOI":"10.1016\/0925-7721(94)00014-X"},{"key":"18_CR6","first-page":"39","volume-title":"Proc. First Workshop on Algorithms and Data Structures (WADS), volume 382 of Lecture Notes in Computer Science","author":"P. F. Dietz","year":"1989","unstructured":"Paul F. Dietz. Optimal algorithms for list indexing and subset rank. In Proc. First Workshop on Algorithms and Data Structures (WADS), volume 382 of Lecture Notes in Computer Science, pages 39\u201346. Springer Verlag, Berlin, 1989."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, and S\u00f8ren Skyum. Dynamic algorithms for the Dyck languages. In Proc. 4th WADS, volume 955 of Lecture Notes in Computer Science, pages 98\u2013108. Springer, 1995.","DOI":"10.1007\/3-540-60220-8_54"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. Dynamic word problems. In Proc 34th FOCS, pages 470\u2013479, 1993.","DOI":"10.1109\/SFCS.1993.366840"},{"key":"18_CR9","unstructured":"Michael L. Fredman and Monika Rauch Henzinger. Lower bounds for fully dynamic connectivity problems in graphs. Manuscript, preliminary version in STOC 94."},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. In Proc. 21st STOC, pages 345\u2013354, 1989.","DOI":"10.1145\/73007.73040"},{"key":"18_CR11","unstructured":"Michael A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, 1978."},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0304-3975(94)90159-7","volume":"130","author":"P. B. Miltersen","year":"1994","unstructured":"P. B. Miltersen, S. Subramanian, J. S. Vitter, and R. Tamassia. Complexity models for incremental computation. Theoretical Computer Science, 130:203\u2013236, 1994.","journal-title":"Theoretical Computer Science"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Peter Bro Miltersen. Lower bounds for union-split-find related problems on random access machines. In Proc. 26th STOC, pages 625\u2013634. ACM, 1994.","DOI":"10.1145\/195058.195415"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. In Proc. 27th STOC, pages 103\u2013111. ACM, 1995.","DOI":"10.1145\/225058.225093"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"issue":"4","key":"18_CR16","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1137\/0218056","volume":"18","author":"F. P. Preparata","year":"1989","unstructured":"Franco P. Preparata and Roberto Tamassia. Fully dynamic point location in a monotone subdivision. SIAM Journal of Computing, 18(4): 811\u2013830, 1989.","journal-title":"SIAM Journal of Computing"},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/BF01840401","volume":"5","author":"R. Tamassia","year":"1990","unstructured":"Roberto Tamassia and Franco P. Preparata. Dynamic maintenance of planar digraphs, with applications. Algorithmica, 5:509\u2013527, 1990.","journal-title":"Algorithmica"},{"key":"18_CR18","unstructured":"Mikkel Thorup. On RAM priority queue. In Proc 7th Ann. Symp. on Discrete Algorithms (SODA), pages 59\u201367, 1996."},{"issue":"3","key":"18_CR19","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A. C. Yao","year":"1981","unstructured":"Andrew Chi-Chih Yao. Should tables be sorted? Journal of the ACM, 28(3): 615\u2013628, July 1981.","journal-title":"Journal of the ACM"}],"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_132.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:06:00Z","timestamp":1605629160000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_132"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_132","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}