{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:07:29Z","timestamp":1725664049973},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582014"},{"type":"electronic","value":"9783540485667"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58201-0_103","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:35:10Z","timestamp":1330270510000},"page":"618-629","source":"Crossref","is-referenced-by-count":3,"title":["A super-logarithmic lower bound for hypercubic sorting networks"],"prefix":"10.1007","author":[{"given":"C. Greg","family":"Plaxton","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Torsten","family":"Suel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"51_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di. Sorting in c log n parallel steps. Combinatorica, 3:1\u201319, 1983.","journal-title":"Combinatorica"},{"key":"51_CR2","first-page":"307","volume":"32","author":"K. E. Batcher","year":"1968","unstructured":"K. E. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computer Conference, vol. 32, pages 307\u2013314, 1968.","journal-title":"Proceedings of the AFIPS Spring Joint Computer Conference"},{"key":"51_CR3","unstructured":"V. Chv\u00e1tal. Lecture notes on the new AKS sorting network. Technical Report DCS-TR-294, Department of Computer Science, Rutgers University, 1992."},{"key":"51_CR4","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1109\/71.159046","volume":"3","author":"P. F. Corbett","year":"1992","unstructured":"P. F. Corbett and I. D. Scherson. Sorting in mesh connected multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 3:626\u2013632, 1992.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"51_CR5","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1137\/0222006","volume":"22","author":"R. E. Cypher","year":"1993","unstructured":"R. E. Cypher. A lower bound on the size of Shellsort sorting networks. SIAM J. Comput., 22:62\u201371, 1993.","journal-title":"SIAM J. Comput."},{"key":"51_CR6","first-page":"58","volume":"22","author":"R. E. Cypher","year":"1993","unstructured":"R. E. Cypher. Theoretical aspects of VLSI pin limitations. SIAM J. Comput., 22:58\u201363, 1993.","journal-title":"SIAM J. Comput."},{"key":"51_CR7","first-page":"501","volume":"47","author":"R. E. Cypher","year":"1993","unstructured":"R. E. Cypher and C. G. Plaxton. Deterministic sorting in nearly logarithmic time on the hypercube and related computers. JCSS, 47:501\u2013548, 1993.","journal-title":"JCSS"},{"key":"51_CR8","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1145\/76359.76362","volume":"36","author":"M. Dowd","year":"1989","unstructured":"M. Dowd, Y. Perl, L. Rudolph, and M. Saks. The periodic balanced sorting network. JACM, 36:738\u2013757, 1989.","journal-title":"JACM"},{"key":"51_CR9","doi-asserted-by":"crossref","unstructured":"M. Kik, M. Kuty\u0142owski, and G. Stachowiak. Periodic constant depth sorting networks. In Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science, pages 201\u2013212, February 1994.","DOI":"10.1007\/3-540-57785-8_142"},{"key":"51_CR10","volume-title":"The Art of Computer Programming, volume 3","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth. The Art of Computer Programming, volume 3. Addison-Wesley, Reading, MA, 1973."},{"key":"51_CR11","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees and Hypercubes","author":"F. T. Leighton","year":"1991","unstructured":"F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees and Hypercubes. Morgan-Kaufmann, San Mateo, CA, 1991."},{"key":"51_CR12","doi-asserted-by":"crossref","unstructured":"F. T. Leighton and C. G. Plaxton. A (fairly) simple circuit that (usually) sorts. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 264\u2013274, October 1990.","DOI":"10.1109\/FSCS.1990.89545"},{"key":"51_CR13","unstructured":"F. T. Leighton and C. G. Plaxton. Hypercubic sorting networks. Unpublished manuscript, August 1993."},{"key":"51_CR14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF01840378","volume":"5","author":"M. S. Paterson","year":"1990","unstructured":"M. S. Paterson. Improved sorting networks with O(log N) depth. Algorithmica, 5:75\u201392, 1990.","journal-title":"Algorithmica"},{"key":"51_CR15","doi-asserted-by":"crossref","unstructured":"C. G. Plaxton. A hypercubic sorting network with nearly logarithmic depth. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 405\u2013416, May 1992.","DOI":"10.1145\/129712.129751"},{"key":"51_CR16","doi-asserted-by":"crossref","unstructured":"C. G. Plaxton, B. Poonen, and T. Suel. Improved lower bounds for Shellsort. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 226\u2013235, October 1992.","DOI":"10.1109\/SFCS.1992.267769"},{"key":"51_CR17","doi-asserted-by":"crossref","unstructured":"C. G. Plaxton and T. Suel. A lower bound for sorting networks based on the shuffle permutation. In Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 70\u201379, June 1992. To appear in Mathematical Systems Theory.","DOI":"10.1145\/140901.140909"},{"key":"51_CR18","volume-title":"Technical Report TR-94-08","author":"C. G. Plaxton","year":"1994","unstructured":"C. G. Plaxton and T. Suel. A super-logarithmic lower bound for hypercubic sorting networks. Technical Report TR-94-08, University of Texas at Austin, Department of Computer Science, April 1994. Available via anonymous ftp from ftp.cs.utexas.edu."},{"key":"51_CR19","unstructured":"V. R. Pratt. Shellsort and Sorting Networks, PhD thesis, Stanford University, Department of Computer Science, December 1971. Also published by Garland, New York, 1979."},{"key":"51_CR20","unstructured":"R. Wanka. Fast general sorting on meshes of arbitrary dimension without routing. Technical Report TR-RI-91-087, Department of Computer Science, University of Paderborn, August 1991."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58201-0_103.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:12:44Z","timestamp":1619572364000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58201-0_103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582014","9783540485667"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-58201-0_103","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}