Efficient Embeddings of Trees in Hypercubes
Sandeep N. Bhatt, Fan Chung, Frank Thomson Leighton, Arnold L. Rosenberg · SIAM Journal on Computing · 1992
The boolean hypercube is a particularly versatile network for parallel computing. It is well known that multidimensional grid machines can be simulated on a hypercube with no communications overhead. In this paper it is shown that every bounded-degree tree can be simulated on the hypercube with constant communications overhead. In fact, the proof shows that every bounded-degree graph with an $O(1)$-separator can be embedded in a hypercube of the same size with dilation and congestion both $O(1)$. It is also proved that not all bounded-degree graphs can be efficiently embedded within the hypercube.