{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:29:12Z","timestamp":1758266952277,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633075"},{"type":"electronic","value":"9783540694229"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63307-3_80","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T19:22:48Z","timestamp":1270495368000},"page":"426-439","source":"Crossref","is-referenced-by-count":4,"title":["Trans-dichotomous algorithms without multiplication \u2014 some upper and lower bounds"],"prefix":"10.1007","author":[{"given":"Andrej","family":"Brodnik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"38_CR1","unstructured":"S. Albers and T. Hagerup. Improved parallel integer sorting without concurrent writting. In 34 rd ACM-SIAM Symposium on Discrete Algorithms, pages 463\u2013472, Orlando, Florida, 1992."},{"key":"38_CR2","doi-asserted-by":"crossref","unstructured":"A. Andersson. Sublogarithmic searching without multiplications. In 36 th IEEE Symposium on Foundations of Computer Science, pages 655\u2013663, 1995.","DOI":"10.1109\/SFCS.1995.492667"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in linear time? In 27 th ACM Symposium on Theory of Computing, pages 427\u2013436, Las Vegas, Nevada, 1995.","DOI":"10.1145\/225058.225173"},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"A. Andersson, P.B. Miltersen, S. Riis, and M. Thorup. Static dictionaries on AC0 RAMs: Query time \u03b8(\u221alog n log log n) is necessary and sufficient. In 37 th IEEE Symposium on Foundations of Computer Science, pages 538\u2013546, Burlington, Ver-mont, 1996.","DOI":"10.7146\/brics.v4i14.21678"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"A.M. Ben-Amram and Z. Galil. When can we sort in o(n log n) time? In 34 th IEEE Symposium on Foundations of Computer Science, pages 538\u2013546, Palo Alto, California, 1993.","DOI":"10.1109\/SFCS.1993.366833"},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"G.S. Brodal. Predecessor queries in dynamic integer sets. In Proceedings 10 th Symposium on Theoretical Aspects of Computer Science. Springer-Verlag, 1997 (To appear).","DOI":"10.1007\/BFb0023445"},{"key":"38_CR7","unstructured":"A. Brodnik. Computation of the least significant set bit. In Proceedings Elec-trotechnical and Computer Science Conference, volume B, pages 7\u201310, Portoroz, Slovenia, 1993."},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"A. Brodnik and J.I. Munro. Membership in a constant time and a minimum space. In Proceedings 2 nd European Symposium on Algorithms, volume 855 of Lecture Notes in Computer Science, pages 72\u201381. Springer-Verlag, 1994.","DOI":"10.1007\/BFb0049398"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"A. Brodnik and J.I. Munro. Neighbours on a grid. In Proceedings 5 th Scandina-vian Workshop on Algorithm Theory, volume 1097 of Lecture Notes in Computer Science, pages 307\u2013320. Springer-Verlag, 1996.","DOI":"10.1007\/3-540-61422-2_141"},{"issue":"2","key":"38_CR10","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J.L. Carter","year":"April 1979","unstructured":"J.L. Carter and M.N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143\u2013154, April 1979.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR11","series-title":"Technical Report","volume-title":"A reliable randomized algorithm for the closest-pair problem","author":"M. Dietzfelbinger","year":"1993","unstructured":"M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen. A reliable randomized algorithm for the closest-pair problem. Technical Report 513, Fachbereich Informatik, Universit\u00e4t Dortmund, Dortmund, Germany, 1993."},{"issue":"3","key":"38_CR12","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"July 1984","unstructured":"M.L. Fredman, J. Koml\u00f3s, and E. Szemer\u00e9di. Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31(3):538\u2013544, July 1984.","journal-title":"Journal of the ACM"},{"key":"38_CR13","doi-asserted-by":"crossref","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. Journal of Computer and System Sciences, 47:424\u2013436, 1993.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"38_CR14","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"June 1994","unstructured":"M.L. Fredman and D.E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences, 48(3):533\u2013551, June 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"38_CR15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"April 1984","unstructured":"M. Furst, J.B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13\u201327, April 1984.","journal-title":"Mathematical Systems Theory"},{"key":"38_CR16","doi-asserted-by":"crossref","unstructured":"J. Almost optimal lower bounds for small depth circuits. In 18 th ACM Symposium on Theory of Computing, pages 6\u201320, Berkeley, California, 1986.","DOI":"10.1145\/12130.12132"},{"key":"38_CR17","doi-asserted-by":"crossref","unstructured":"P.B. Miltersen. Lower bounds for static dictionaries on RAMS with bit operations but no multiplication. In Proceedings 23 rd International Colloquium on Automata, Languages and Programming, volume 1099 of Lecture Notes in Computer Science, pages 442\u2013451. Springer-Verlag, 1996.","DOI":"10.1007\/3-540-61440-0_149"},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"R. Raman. Priority queues: Small, monotone, and Tans-dichotomus. In Proceed-ings 4 th European Symposium on Algorithms, volume 1136 of Lecture Notes in Computer Science, pages 121\u2013137. Springer-Verlag, 1996.","DOI":"10.1007\/3-540-61680-2_51"},{"key":"38_CR19","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Sch\u00f6nhage","year":"1971","unstructured":"A. Sch\u00f6nhage and V. Strassen. Schnelle Multiplikation gro\u00dfer Zahlen. Computing, 7:281\u2013292, 1971.","journal-title":"Computing"},{"key":"38_CR20","unstructured":"M. Thorup. On RAM priority queues. In 7 th CM-SIAM Symposium on Discrete Algorithms, pages 59\u201367, Atlanta, Georgia, 1996."},{"key":"38_CR21","unstructured":"M. Thorup. Randomized sorting in O (n log log n) time and linear space using addition, shift, and bit-wise booleaan operations. In 8 th ACM-SIAM Symposium on Discrete Algorithms, pages 352\u2013359, New Orleans, Louisiana, 1997."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63307-3_80","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T21:15:23Z","timestamp":1739999723000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63307-3_80"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633075","9783540694229"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-63307-3_80","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}