{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:33Z","timestamp":1742617113245,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_15","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:36:36Z","timestamp":1330270596000},"page":"167-171","source":"Crossref","is-referenced-by-count":1,"title":["Lower bounds for dynamic algorithms"],"prefix":"10.1007","author":[{"given":"Michael L.","family":"Fredman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"issue":"3","key":"15_CR1","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF02126797","volume":"8","author":"M. Ajtai","year":"1988","unstructured":"M. Ajtai: A lower bound for finding predecessors in Yao's cell probe model. Combinatorica 8, 3 (1988) 235\u2013247","journal-title":"Combinatorica"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Amram, A., Galil, Z: Lower bounds for data structure problems on RAMs. Proceedings of the 32nd Symposium on Foundations of Computer Science (1991), 622\u2013631","DOI":"10.1109\/SFCS.1991.185428"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Dietz, P.: Optimal algorithms for list indexing and subset rank. Algorithms and data structures: Workshop WADS '89, Ottawa, Canada (1989), 39\u201346","DOI":"10.1007\/3-540-51542-9_5"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnhert, H. and Tarjan, R.: Dynamic perfect hashing: upper and lower bounds. Proceedings of the 29th Symposium on Foundations of Computer Science (1988), 524\u2013531","DOI":"10.1109\/SFCS.1988.21968"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas Van","year":"1977","unstructured":"Van Emde Boas, P., Kaas, R., and Zijlstra, E.: Design and implementation of an efficient priority queue. Math. Systems Theory 10 (1977), 99\u2013127","journal-title":"Math. Systems Theory"},{"key":"15_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","volume":"13","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Italiano, G., Tamassia, R., Tarjan, R., Westbrook, J., and Yung, M.: Maintenance of a minimum spanning forest in a dynamic planar graph. J. Algorithms 13 (1992), 33\u201354","journal-title":"J. Algorithms"},{"key":"15_CR7","unstructured":"Fredman, M., Johnson, D. S., McGeoch, L. A., and Ostheimer, G.: Data structures for traveling salesmen. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (1993), 145\u2013154"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. Proceedings of the 21st Annual ACM Symposium on Theory of Computing (1989), 345\u2013354","DOI":"10.1145\/73007.73040"},{"issue":"3","key":"15_CR9","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M. Fredman","year":"1993","unstructured":"Fredman, M., Willard, D.: Surpassing the information theoretic bound with fusion trees. J. Computer and System Sciences 47, 3 (1993), 424\u2013436","journal-title":"J. Computer and System Sciences"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Hampapuram, H., Fredman, M.: Optimal bi-weighted binary trees and the complexity of maintaining partial sums. Proceedings of the 34th Symposium on Foundations of Computer Science (1993), 480\u2013485","DOI":"10.1109\/SFCS.1993.366839"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"LaPoutre, J.: Lower bounds for the union-find and the split-find problem on pointer machines. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (1990), 34\u201344.","DOI":"10.1145\/100216.100221"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Rauch, M.: Improved data structures for fully dynamic biconnectivity. Proceedings of the 26th Annual ACM Symposium on Theory of Computing (1994), to appear","DOI":"10.1145\/195058.195434"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Sundar, R.: A lower bound for the dictionary problem under a hashing model, Proceedings of the 32nd Symposium on Foundations of Computer Science (1991), 612\u2013621; and personal communication","DOI":"10.1109\/SFCS.1991.185427"},{"key":"15_CR14","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D. Willard","year":"1983","unstructured":"Willard, D.: Log-logarithmic worst case range queries are possible in space O(N). Information Processing Letters 17 (1983), 81\u201389","journal-title":"Information Processing Letters"},{"key":"15_CR15","volume-title":"Doctoral Dissertation","author":"B. Xiao","year":"1992","unstructured":"Xiao, B.: New bounds in cell probe model. Doctoral Dissertation, University of California, San Diego, 1992"},{"issue":"3","key":"15_CR16","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A. Yao","year":"1981","unstructured":"Yao, A.: Should tables be sorted? J. Assoc. Comput. Mach. 28, 3 (1981), 615\u2013628","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:23:39Z","timestamp":1742595819000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}