Efficient Embeddings of Trees in Hypercubes
- 1 February 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (1) , 151-162
- https://doi.org/10.1137/0221012
Abstract
THE BOOLEAN HYPERCUBE IS A PARTICULARLY VERSATILE NETWORK FOR PARALLEL COMPUTING. IT IS WELL KNOWN THAT MULTI-DIMENSIONAL GRID MACHINES CAN BE SIMULATED ON A HYPERCUBE WITH NO COMMUNICATIONS OVERHEAD. IN THIS PAPER WE SHOW THAT EVERY BOUNDED-DEGREE TREE CAN BE SIMULATED ON THE HYPERCUBE WITH CONSTANT COMMUNICATIONS OVERHEAD. OUR PROOF IN FACT SHOWS THAT EVERY BOUNDED-DEGREE GRAPH WITH AN 0(1)-SEPARATOR CAN BE EMBEDDED IN A HYPERCUBE OF THE SAME SIZE WITH DILATION AND CONGESTION BOTH 0(1). WE PROVE ALSO THAT NOT ALL BOUNDED-DEGREE GRAPHS CAN BE EFFICIENTLY EMBEDDED WITHIN THE HYPERCUBE.Keywords
This publication has 11 references indexed in Scilit:
- Simulating binary trees on hypercubesPublished by Springer Nature ,2006
- Optimal emulations by butterfly-like networksJournal of the ACM, 1996
- Optimal embeddings of butterfly-like graphs in the hypercubeTheory of Computing Systems, 1990
- Universal Graphs for Bounded-Degree Trees and Planar GraphsSIAM Journal on Discrete Mathematics, 1989
- On mapping parallel algorithms into parallel architecturesJournal of Parallel and Distributed Computing, 1987
- Communication efficient basic linear algebra computations on hypercube architecturesJournal of Parallel and Distributed Computing, 1987
- Expanding graphs contain all small treesCombinatorica, 1987
- Hypercubes and PyramidsPublished by Springer Nature ,1986
- A framework for solving VLSI graph layout problemsJournal of Computer and System Sciences, 1984
- On the Mapping ProblemIEEE Transactions on Computers, 1981