Embedding complete binary trees in product graphs

This paper shows how to embed complete binary trees in products of complete binary trees, products of shuffle-exchange graphs, and products of de Brui jn graphs with small dilation and congestion. In the embedding results pres ented here the size of the host graph can be fixed to an arbitrary size, wh ile we define no bound on the size of the guest graph. This is motivated by the fact that the host architecture has a fixed number of processors due t o its physical design, while the guest graph can grow arbitrarily large dep ending on the application. The results of this paper widen the class of com putations that can be performed on these product graphs which are often cit ed as being low-cost alternatives for hypercubes.