{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T14:10:04Z","timestamp":1737123004170,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438663"},{"type":"electronic","value":"9783540454717"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45471-3_1","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T17:18:22Z","timestamp":1179767902000},"page":"1-18","source":"Crossref","is-referenced-by-count":0,"title":["An Efficient Quasidictionary"],"prefix":"10.1007","author":[{"given":"Torben","family":"Hagerup","sequence":"first","affiliation":[]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1006\/jcss.1998.1580","volume":"57","author":"A. Andersson","year":"1998","unstructured":"A. Andersson, T. Hagerup, S. Nilsson, and R. Raman, Sorting in linear time?, J. Comput. System Sci. 57 (1998), pp. 74\u201393.","journal-title":"J. Comput. System Sci."},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"A. Andersson, P. B. Miltersen, S. Riis, and M. Thorup, Static dictionaries on AC 0 RAMs: Query time \u0398(\u221alogn\/loglogn) is necessary and sufficient, Proc., 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1996), pp. 441\u2013450.","DOI":"10.1109\/SFCS.1996.548503"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"A. Andersson and M. Thorup, Tight(er) worst-case bounds on dynamic searching and priority queues, Proc., 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), pp. 335\u2013342.","DOI":"10.1145\/335305.335344"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"P. Beame and F. E. Fich, Optimal bounds for the predecessor problem, Proc., 31st Annual ACM Symposium on Theory of Computing (STOC 1999), pp. 295\u2013304.","DOI":"10.1145\/301250.301323"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"M. R. Brown and R. E. Tarjan, A representation for linear lists with movable fingers, Proc., 10th Annual ACM Symposium on Theory of Computing (STOC 1978), pp. 19\u201329.","DOI":"10.1145\/800133.804328"},{"key":"1_CR6","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms (1st edition), The MIT Press, Cambridge, MA, 1990.","edition":"1st edition"},{"key":"1_CR7","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"2001","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (2nd edition), The MIT Press, Cambridge, MA, 2001.","edition":"2nd edition"},{"key":"1_CR8","unstructured":"E. D. Demaine, A threads-only MPI implementation for the development of parallel programs, Proc., 11th International Symposium on High Performance Computing Systems (HPCS 1997), pp. 153\u2013163."},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M. Dietzfelbinger","year":"1994","unstructured":"M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan, Dynamic perfect hashing: Upper and lower bounds, SIAM J. Comput. 23 (1994), pp. 738\u2013761.","journal-title":"SIAM J. Comput."},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization problems, J. ACM 34 (1987), pp. 596\u2013615.","journal-title":"J. ACM"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M. L. Fredman","year":"1993","unstructured":"M. L. Fredman and D. E. Willard, Surpassing the information theoretic bound with fusion trees, J. Comput. System Sci. 47 (1993), pp. 424\u2013436.","journal-title":"J. Comput. System Sci."},{"key":"1_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, New York, 1979."},{"key":"1_CR13","unstructured":"J. Gergov, Algorithms for compile-time memory optimization, Proc., 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 907\u2013908."},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"L. J. Guibas and R. Sedgewick, A dichromatic framework for balanced trees, Proc., 19th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1978), pp. 8\u201321.","DOI":"10.1109\/SFCS.1978.3"},{"key":"1_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1007\/BFb0028575","volume-title":"Proc., 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998)","author":"T. Hagerup","year":"1998","unstructured":"T. Hagerup, Sorting and searching on the word RAM, Proc., 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998), Lecture Notes in Computer Science, Springer-Verlag, Berlin, Vol. 1373, pp. 366\u2013398."},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T. Hagerup","year":"2001","unstructured":"T. Hagerup, P. B. Miltersen, and R. Pagh, Deterministic dictionaries, J. Algorithms 41 (2001), pp. 69\u201385.","journal-title":"J. Algorithms"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"S. Huddleston and K. Mehlhorn, A new data structure for representing sorted lists, Acta Inf. 17 (1982), pp. 157\u2013184.","journal-title":"Acta Inf."},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"M. G. Luby, J. Naor, and A. Orda, Tight bounds for dynamic storage allocation, Proc., 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1994), pp. 724\u2013732.","DOI":"10.1137\/S089548019325647X"},{"key":"1_CR19","unstructured":"K. Mehlhorn and S. N\u00e4her, LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, 1999."},{"key":"1_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/3-540-61680-2_51","volume-title":"Proc., 4th Annual European Symposium on Algorithms (ESA 1996)","author":"R. Raman","year":"1996","unstructured":"R. Raman, Priority queues: Small, monotone and trans-dichotomous, Proc., 4th Annual European Symposium on Algorithms (ESA 1996), Lecture Notes in Computer Science, Springer-Verlag, Berlin, Vol. 1136, pp. 121\u2013137."},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1145\/321650.321658","volume":"18","author":"J. M. Robson","year":"1971","unstructured":"J. M. Robson, An estimate of the store size necessary for dynamic storage allocation, J. ACM 18 (1971), pp. 416\u2013423.","journal-title":"J. ACM"},{"key":"1_CR22","first-page":"491","volume":"21","author":"J. M. Robson","year":"1974","unstructured":"J. M. Robson, Bounds for some functions concerning dynamic storage allocation, J. A CM 21 (1974), pp. 491\u2013499.","journal-title":"J. A CM"},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/S0097539795288246","volume":"30","author":"M. Thorup","year":"2000","unstructured":"M. Thorup, On RAM priority queues, SIAM J. Comput. 30 (2000), pp. 86\u2013109.","journal-title":"SIAM J. Comput."},{"key":"1_CR24","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Proc., International Workshop on Memory Management (IWMM 1995)","author":"P. R. Wilson","year":"1995","unstructured":"P. R. Wilson, M. S. Johnstone, M. Neely, and D. Boles, Dynamic storage allocation: A survey and critical review, Proc., International Workshop on Memory Management (IWMM 1995), Lecture Notes in Computer Science, Springer-Verlag, Berlin, Vol. 986, pp. 1\u2013116."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45471-3_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T14:39:17Z","timestamp":1737038357000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45471-3_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438663","9783540454717"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-45471-3_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}