Work-preserving emulations of fixed-connection networks

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. J. Atallah, On Multidimensional Arrays of Processors, IEEE Transactions on Computers, v.37 n.10, p.1306-1309, October 1988 [doi>10.1109/12.5995]
	2	BENEg, V.E. 1965. Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, Orlando, Fla.
	3	Sandeep N. Bhatt , Fan R. K. Chung , Jia-Wei Hong , F. Thomson Leighton , Bojana Obrenic , Arnold L. Rosenberg , Eric J. Schwabe, Optimal emulations by butterfly-like networks, Journal of the ACM (JACM), v.43 n.2, p.293-330, March 1996 [doi>10.1145/226643.226658]
	4	BHATT, S. N., CHUNG, F. R. K., LEIGHTON, F. T., AND ROSENBERG, A. L. 1986. Optimal simulations of tree machines. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (Oct.). IEEE, New York.
	5	S. N. Bhatt , F. R.K. Chung , F. T. Leighton , A. L. Rosenberg, Efficient Embeddings of Trees in Hypercubes, University of Massachusetts, Amherst, MA, 1988
	6	Richard J. Cole , Bruce M. Maggs , Ramesh K. Sitaraman, On the benefit of supporting virtual channels in wormhole routers, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.131-141, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237517]
	7	FELLOWS, M.R. 1985. Encoding graphs in graphs. Ph.D. dissertation, Department of Computer Science. Univ. California, San Diego, San Diego, Calif.
	8	FISHBURN, J. P., AND FINKEL, R.A. 1982. Quotient networks. IEEE Trans. Comput. C-31, 4 (Apr.). 288 -295.
	9	GREENBERG, D. S., HEATH, L. S., AND ROSENBERG, A.L. 1990. Optimal embeddings of butterflylike graphs in the hypercube. Math. Syst. Theory 23, 61-77.
	10	HOLY, D., AND LEISERSON, C.E. 1980. A layout for the shuffle-exchange network. In Proceedings ~of the 1980 International Conference on Parallel Processing (Aug.). IEEE, New York, pp. 329-336.
	11	Daniel Kleitman , Frank Thomson Leighton , Margaret Lepley , Gary L. Miller, New layouts for the shuffle-exchange graph(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.278-292, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802480]
	12	Clyde P. Kruskal , Larry Rudolph , Marc Snir, A Complexity Theory of Efficient Parallel Algorithms (Extended Abstract), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.333-346, July 11-15, 1988
	13	Frank Thomson Leighton , Margaret Lepley , Gary L. Miller, Layouts for the shuffle-exchange graph based on the complex plane diagram, SIAM Journal on Algebraic and Discrete Methods, v.5 n.2, p.202-215, June 1984 [doi>10.1137/0605021]
	14	F. T. Leighton , Bruce M. Maggs , Abhiram G. Ranade , Satish B. Rao, Randomized routing and sorting on fixed-connection networks, Journal of Algorithms, v.17 n.1, p.157-205, July 1994 [doi>10.1006/jagm.1994.1030]
	15	LEIGHTON, F. T., AND MILLER, G.L. 1981. Optimal layouts for small shuffle-exchange graphs. In VLSI 81-Very Large Scale Integration, J. Gray, ed. Academic Press, New York, NY.
	16	LEIGHTON, T., MAGGS, B., AND RAO, S. 1988. Universal packet routing algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science (Oct.). IEEE, New York, pp. 256-271.
	17	MEYER AUF DER HEIDE, F. 1983. Efficiency of universal parallel computers. Acta Inf. 19, 269-296.
	18	Friedhelm Meyer auf der Heide, Efficient simulations among several models of parallel computers, SIAM Journal on Computing, v.15 n.1, p.106-119, Feb. 1986 [doi>10.1137/0215008]
	19	F. M. auf der Heide , R. Wanka, Time-optimal simulations of networks by universal parallel computers, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science on STACS 89, p.120-131, February 1989, Paderborn, Germany
	20	LEWIS II, P. M., STEARNS, R. E., AND HARTMANIS, J. 1965. Memory bounds for recognition of context-free and context-sensitive languages. In Proceedings of the IEEE Symposium on Circuit Theory and Logical Design. IEEE, New York, pp. 191-202.
	21	Christos Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.510-513, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62262]
	22	M. S. Paterson , W. L. Ruzzo , L. Snyder, Bounds on minimax edge length for complete binary trees, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.293-299, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802481]
	23	PIPPENGER, N. 1982. Telephone switching networks. In Proceedings of Symposia in Applied Mathematics, vol. 26. American Mathematical Society, Providence, R.I., pp. 101-133.
	24	PIPPENGER, N. 1984. Parallel communication with limited buffers. In Proceedings of the 25th ~Annual Symposium on Foundations of Computer Science (Oct.). IEEE, New York, pp. 127-136.
	25	RAGHUNATHAN, A., AND SARAN, n. 1988. Is the shuffle-exchange better than the butterfly? Unpublished manuscript.
	26	John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987 [doi>10.1145/7531.7532]
	27	SEKANINA, M. 1960. On an ordering of the set of vertices of a connected graph. Publications of the Faculty of Science, University of Brno 412, 137-142.
	28	STEINBERG, D., AND RODEH, M. 1981. A layout for the shuffle-exchange network with ~(N2/log3/2 N) area. IEEE Trans. Comput. C-30, 12 (Dec.). 977-982.
	29	Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]
	30	WISE, D.S. 1981. Compact layouts of Banyan/FFT networks. In CMU Conference on VLSI Systems and Computations, H. T. Kung, B. Sproull, and G. Steele, eds. Computer Science Press, Rockville, Md., pp. 186-195.

Collaborative Colleagues:

Richard R. Koch: colleagues

F. T. Leighton: colleagues

Bruce M. Maggs: colleagues

Satish B. Rao: colleagues

Arnold L. Rosenberg: colleagues

Eric J. Schwabe: colleagues