Embedding hyperpyramids into hypercubes
C. T. Howard Ho, S. Lennart Johnsson · IBM Journal of Research and Development · 1994
A ̂P(k, d) hyperpyramid is a level structure of k hypercubes, where the hypercube at level i is of dimension id, and a node at level i - 1 is connected to every node in a d-dimensional subcube at level i, except for the leaf level k. Hyperpyramids contain pyramids as proper subgraphs. We show that a hyperpyramid P(k, d) can be embedded in a hypercube with minimal expansion and dilation = d. The congestion is bounded from above by ⌈(2d- 1)/d⌉ and from below by 1 + ⌈(2d- d)/(kd + 1)⌉. We also present embeddings of a hyperpyramid ̂(k, d) together with (2d- 2) hyperpyramids ̂(k - 1, d) such that only one hypercube node is unused. The dilation of the embedding is d + 1, with a congestion of O(2d). A corollary is that a complete n-ary tree can be embedded in a hypercube with dilation = max(2,⌈log2n⌉) and expansion = equation (n - 1)/(nk+1- 1).