A lower bound for sorting networks based on the shuffle permutation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A lower bound for sorting networks based on the shuffle permutation

Full text

Pdf (904 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures table of contents

San Diego, California, United States

Pages: 70 - 79

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

C. Greg Plaxton
Torsten Suel

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 8, Citation Count: 0

Additional Information:

references index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/140901.140909 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
	2	K. E. Batcher. Sorting networks and their applications, in Proceedings of the AFIPS Spring Joint Computer Conference, vo}. 32, pages 307- 314, 1968.
	3	R. Cypher, A lower bound on the size of shellsort networks, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.58-63, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72942]
	4	R. E. Cypher. Theoretical aspects of VLSI pin limitations. Technical Report RJ7115, IBM Almaden Research Center, November 1989.
	5	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	6	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	7	F. T. Leighton and C. G. Plaxton. A (fairly) simple circuit that (usually) sorts. In Proceedings o/ the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 264-274, October 1990.
	8	M. S. Paterson. Improved sorting networks with O(logn) depth. Algorithmica, 5:75-92, 1990.
	9	C. Greg Plaxton, A hypercubic sorting network with nearly logarithmic depth, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.405-416, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129751]
	10	František Soviš, On rearrangeable networks of the shuffle-exchange type, Computers and Artificial Intelligence, v.7 n.4, p.359-373, 1988