Dilation d Embeddings of a Hyper–Pyramid into a Hypercube
1989 (English)Conference paper (Refereed)
A P(k, d) hyper-pyramid is a level structure of k Boolean cubes where the cube at level i is of dimension id, and a node at level i - 1 connects to every node in a d dimensional Boolean subcube at level i, except for the leaf level k. Hyper-pyramids contain pyramids as proper subgraphs. We show that a P(k, d) hyper-pyramid can be embedded in a Boolean cube with minimal expansion and dilation d. The congestion is bounded from above by 2d+1/d+2 and from below by 1 + 2d-d/kd+1. For P(k, 2) hyper-pyramids we present a dilation 2 and congestion 2 embedding. As a corollary a complete n-ary tree can be embedded in a Boolean cube with dilation max(2, log2n) and expansion 2klog2n + 1/nk+1-1/n-1. We also discuss multiple pyramid embeddings.
Place, publisher, year, edition, pages
1989. 294-303 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-65556DOI: 10.1145/76263.76295OAI: oai:DiVA.org:kth-65556DiVA: diva2:483465
NR 201408052012-01-252012-01-25Bibliographically approved