On probabilistic networks for selection, merging, and sorting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On probabilistic networks for selection, merging, and sorting

Full text

Pdf (1.31 MB)

Source

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

Santa Barbara, California, United States

Pages: 106 - 118

Year of Publication: 1995

ISBN:0-89791-717-0

Authors

Tom Leighton	Department of Mathematics and Laboratory for Computer Science, MIT, Cambridge, MA
Yuan Ma	Department of Computer Science, Stanford University, Stanford, CA
Torsten Suel	NEC Research Institute, 4 Independence Way, Princeton, NJ

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
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): 1, Downloads (12 Months): 16, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

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/215399.215429 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. Koml6s, M. S. Paterson, and E. Szemer#di, k-sorting. In preparation.
	2	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	3	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]
	4	M. Ajtai, J. Komlds, and E. Szemer#di. Halvers and expanders. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 686-689, October 1992.
	5	V. E. Alekseyev. Sorting algorithms with minimum memory. Kibernetika, 5:99-103, 1969.
	6	N. Alon and J. H. Spencer. The Probabihst#c Method. Wiley-Interscience, New York, NY, 1991.
	7	K. E. Batcher. Sorting networks and their apphcations. In Proceedings of the A FIPS Spring Joint Computer Conference, volume 32, pages 307-314, 1968.
	8	Takahiro Ikeda, A Probabilistic Selection Network with Butterfly Networks, Proceedings of the 4th International Symposium on Algorithms and Computation, p.267-276, December 15-17, 1993
	9	Shuji Jimbo , Akira Maruoka, Selection Networks with 8n log2n Size and O(log n) Depth, Proceedings of the Third International Symposium on Algorithms and Computation, p.165-174, December 16-18, 1992
	10	N. Kahale. Eigenvalues and expansion of regular graphs. Technical Report 93-70R, DIMACS, Rutgers University, 1993.
	11	Nabil Kahale , Tom Leighton , Yuan Ma , C. Greg Plaxton , Torsten Suel , Endre Szemerédi, Lower bounds for sorting networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.437-446, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225178]
	12	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
	13	E. A. Lamagna The complexity of monotone networks for certain bilinear forms, routing problems, sorting, and merging. IEEE Trans. Comput., 28:773- 782, 1979.
	14	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	15	Tom Leighton , Yuan Ma , C. Greg Plaxton, Highly fault-tolerant sorting circuits, Proceedings of the 32nd annual symposium on Foundations of computer science, p.458-469, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185406]
	16	T. Leighton and C. G. Plaxton. A (fairly) simple circuit that (usually) sorts, in Proceedings of the 31st Annual IEEE Symposzum on Foundatwns of Computer Science, pages 458-469, October 1990.
	17	Yuan Ma, Fault-tolerant sorting networks, Massachusetts Institute of Technology, Cambridge, MA, 1995
	18	P. B. Miltersen, M. S. Paterson, and J. Tarui. The asymptotic complexity of merging networks. In Proceedings of the 33rd Annual IEEE Symposzum on Foundations of Computer Sczence, pages 236-246, October 1992.
	19	Nicholas Pippenger, Communication networks, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	20	Nicholas Pippenger, Selection networks, SIAM Journal on Computing, v.20 n.5, p.878-887, Oct. 1991 [doi>10.1137/0220054]
	21	Nicholas Pippenger , Leslie G. Valiant, Shifting Graphs and Their Applications, Journal of the ACM (JACM), v.23 n.3, p.423-432, July 1976 [doi>10.1145/321958.321962]
	22	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]
	23	Christine Rüb, Lower bounds for merging on the hypercube, Proceedings of the second Italian conference on Algorithms and complexity, p.213-222, March 1994, Rome, Italy
	24	C. Riib. On the average running time of odd-even merge sort. In Proceedings of the 12th Symposium on Theoretzcal Aspects of Computer Sczence, Sponger LNCS 900, pages 491-502, February 1995.
	25	R. Seclsewick Data movement in odd-even merging. SIAM J. Comput., 7:239-272, 1978.
	26	A. C. Yao. Bounds on selection networks. SIAM J. Comput.# 9:566-582, 1980.
	27	Andrew Chi-Chih Yao , Foong Frances Yao, Lower Bounds on Merging Networks, Journal of the ACM (JACM), v.23 n.3, p.566-571, July 1976 [doi>10.1145/321958.321976]