Taking random walks to grow trees in hypercubes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Taking random walks to grow trees in hypercubes

Full text

Pdf (1.35 MB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 3 (July 1993) table of contents

Pages: 741 - 764

Year of Publication: 1993

ISSN:0004-5411

Authors

Sandeep Bhatt	Bellcore, Morristown, NJ
Jin-Yi Cai	Princeton Univ., Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 28, Citation Count: 9

Additional Information:

references cited by index terms review 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/174130.174144 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	~ALDOUS, D. Minimization algorithms and random walk on the d-cube. Ann. Prob. H, 2 ~(1983), 403-413.
	2	~BHATT, S. N., CHUNG, F. R. K., LEIGHTON, F. T., AND ROSENBERG. A.L. Optimal simulations ~of tree machines. In Proceedings of the 27th Annual IEEE Symposmm on Foundations of ~Computer Science. IEEE, New York, 1986, pp. 274-282.
	3	~BHATT, S. N., AND IPSEN, I. How to embed trees in hypercubes. Yale Univ. Res. Rep. ~RR-443.
	4	~CHAN, M.Y. Dilation-2 embeddings of grids into hypercubes. In Proceedings of the Interna- ~tional Conference on Parallel Processing. SIAM, Philadelphia, Pa., 1988, pp. 295-298.
	5	~CYBENKO, G. Dynamic load balancing for distributed memory multiprocessors. Tech. Rep. ~87-1. Tufts Univ., Medford, Mass., 1987.
	6	Derek L. Eager , Edward D. Lazowska , John Zahorjan, Adaptive load sharing in homogeneous distributed systems, IEEE Transactions on Software Engineering, v.12 n.5, p.662-675, May 1986
	7	~GREENBERG, D. S., HEATH, L. S., AND ROSENBERG, A.L. Optimal embeddings of butterfly- ~like graphs in the hypercube. Math. Syst. Theory 23 (1990), 61-77.
	8	~no, C. T., AND JOHNSSON, S.L. Spanning balanced trees in Boolean cubes. Yale Univ. Tech. ~ Rep. 508.
	9	~HoNo, J.~W., TAN, X., AND CHEN, M. Dynamic cyclic load balancing on hypcrcubcs. In ~Proceedings of the 4th Conference on Hypercubes, Concurrent Computers, and Applications, vol. ~1. Golden Gate Enterprises, Los Altos, Calif., 1989, pp. 595-598.
	10	S. Lennart Johnsson, Communication effect basic linear algebra computations on hypercube architectures, Journal of Parallel and Distributed Computing, v.4 n.2, p.133-172, April 1, 1987 [doi>10.1006/jpdc.1997.1353]
	11	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]
	12	T. Leighton , M. Newman , A. G. Ranade , E. Schwabe, Dynamic tree embeddings in butterflies and hypercubes, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.224-234, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72959]
	13	~LETAC, G., AND TAKACS, L. Random walks on an m-dimensional cube. J. Reine Angew Math. ~310 (1979), 187-195.
	14	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 [doi>10.1145/113379.113383]
	15	Charles L. Sietz, Multicomputers, Developments in concurrency and communication, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991

CITED BY 9

	Keqin Li, Performance evaluation of probabilistic tree embedding in cube-connected cycles, Proceedings of the 1998 ACM symposium on Applied Computing, p.584-592, February 27-March 01, 1998, Atlanta, Georgia, United States
	Keqin Li, On dynamic tree growing in hypercubes, Proceedings of the 1997 ACM symposium on Applied computing, p.496-503, April 1997, San Jose, California, United States
	Jaafar Gaber , Bernard Toursel, Randomized load distribution of arbitrary trees in distributed networks, Proceedings of the 1998 ACM symposium on Applied Computing, p.564-568, February 27-March 01, 1998, Atlanta, Georgia, United States
	Keqin Li, Maintenance of tree structured computations on parallel and distributed computer systems, Proceedings of the 1996 ACM symposium on Applied Computing, p.337-343, February 17-19, 1996, Philadelphia, Pennsylvania, United States
	Keqin Li, On the performance of randomized embedding of reproduction trees in static networks, International Journal of Parallel Programming, v.31 n.5, p.393-406, October 2003
	Keqin Li, Analysis of randomized load distribution for reproduction trees in linear arrays and rings, Theoretical Computer Science, v.321 n.2-3, p.195-214, 16 August 2004
	Ralf Klasing, Improved Compressions of Cube-Connected Cycles Networks, IEEE Transactions on Parallel and Distributed Systems, v.9 n.8, p.803-812, August 1998
	Volker Heun , Ernst W. Mayr, Efficient dynamic embeddings of binary trees into hypercubes, Journal of Algorithms, v.43 n.1, p.51-84, April 2002
	Keqin Li, Design and analysis of asymptotically optimal randomized tree embedding algorithms in static networks, Performance Evaluation, v.60 n.1-4, p.141-163, May 2005

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.2 Graph Theory
Subjects: Graph algorithms

Additional Classification:
C. Computer Systems Organization
C.1 PROCESSOR ARCHITECTURES
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures

G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.1 Combinatorics
Subjects: Combinatorial algorithms

General Terms:
Algorithms, Design, Theory

Keywords:
computation trees, hypercube architectures, online embedding, probabilistic analysis

REVIEW

"Mukkai S. Krishnamoorthy : Reviewer"

A simple strategy to maintain dynamically evolving trees on fine-grain parallel architectures is discussed in this fine paper. As a computation or data structure evolves, the corresponding tree grows and shrinks dynamically. Since the shape an more...

Collaborative Colleagues:

Sandeep Bhatt: colleagues

Jin-Yi Cai: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player