Dynamic tree embeddings in butterflies and hypercubes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamic tree embeddings in butterflies and hypercubes

Full text

Pdf (1.36 MB)

Source

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

Santa Fe, New Mexico, United States

Pages: 224 - 234

Year of Publication: 1989

ISBN:0-89791-323-X

Authors

T. Leighton	M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MA
M. Newman	M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MA
A. G. Ranade	Department of EECS, University of California, Berkeley, CA
E. Schwabe	M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MA

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): 1, Downloads (12 Months): 13, Citation Count: 10

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/72935.72959 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	1. S. N. Bhatt and Jin-Yi Cal. Take a Walk, Grow a Tree. In Proceedings of FOCS, pages 469-478, 1988. To appear.
	2	Sandeep Bhatt , Fan Chung , Jia-Wei Hong , Arnold Rosenberg, Optimal simulations by Butterfly Networks, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.192-204, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62229]
	3	[3] S. N. Bhatt, F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg. Optimal simulations of tree machines. In Proceedings of FOCS, pages 274-282, 1986.
	4	[4] S. N. Bhatt and I. Ipsen. How to embed trees in hypercubes. Technical Report 443, Yale University, 1985.
	5	[5] M. Y. Chan., Dilation-2 Embeddings of Grids into Hypercubes. Technical Report UTDCS 1-88, The University of Texas at Dallas, 1988.
	6	[6] D. S. Greenberg, L. S. Heath, and A. L. Rosenberg. Optimal embeddings of the FFT graph in the Hypercube. 1987. Typescript, University of Massachusetts.
	7	[7] C. T. Ho and S. L. Johnsson. Embedding Generalized Pyramids in Hypercubes. Technical Report, Yale University, 1988. In preparation.
	8	[8] W. Hoeffding. On the distribution of the number of successes in independent trials. Annals of Mathematical Statistics, 27:713-721, 1956.
	9	Richard Karp , Yanjun Zhang, A randomized parallel branch-and-bound procedure, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.290-300, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62240]
	10	R. Koch , T. Leighton , B. Maggs , S. Rao, Work-preserving emulations of fixed-connection networks, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.227-240, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73029]

CITED BY 10

	Bhaskar Ghosh , S. Muthukrishnan, Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.226-235, June 27-29, 1994, Cape May, New Jersey, United States
	Bill Aiello , Tom Leighton, Coding theory, hypercube embeddings, and fault tolerance, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.125-136, July 21-24, 1991, Hilton Head, South Carolina, United States
	Sandeep Bhatt , David Greenberg , Tom Leighton , Pangfeng Liu, Tight bounds for on-line tree embeddings, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.344-350, January 28-30, 1991, San Francisco, California, United States
	Abhiram Ranade, Optimal speedup for backtrack search on a butterfly network, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.40-48, July 21-24, 1991, Hilton Head, South Carolina, United States
	Abhiram Ranade, Maintaining dynamic ordered sets on processor networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.127-137, June 29-July 01, 1992, San Diego, California, United States
	Robert D. Blumofe , Charles E. Leiserson, Space-efficient scheduling of multithreaded computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.362-371, May 16-18, 1993, San Diego, California, United States
	Christos Kaklamanis , Giuseppe Persiano, Branch-and-bound and backtrack search on mesh-connected arrays of processors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.118-126, June 29-July 01, 1992, San Diego, California, United States
	Sandeep Bhatt , Jin-Yi Cai, Taking random walks to grow trees in hypercubes, Journal of the ACM (JACM), v.40 n.3, p.741-764, July 1993
	Michael A. Palis , Jing-Chiou Liou , David S. L. Wei, Task Clustering and Scheduling for Distributed Memory Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, v.7 n.1, p.46-55, January 1996
	Bethany M. Y. Chan , Francis Y. L. Chin , Chung-Keung Poon, Optimal Simulation of Full Binary Trees on Faulty Hypercubes, IEEE Transactions on Parallel and Distributed Systems, v.6 n.3, p.269-286, March 1995