Embedding the Complete Tree in the Hypercube

✍ Scribed by A.S. Wagner

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 453 KB
• Volume: 20
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1994.1023

✦ Synopsis

Let (H_{n}) be the (n)-dimensional boolean hypercube with (2^{n}) vertices labeled (\left{0,1, \ldots 2^{n}-1\right}), with an edge between two vertices whenever their Hamming distance is 1. We describe a spanning tree (T_{n}) of (H_{n}) with the following properties. (T_{n}) is complete for the first (n-2) levels with the remaining nodes on level (n) and (n-1) of the tree. Except for levels (n) and (n-1), there is a dilation 2 embedding of (H_{k}) on level (k) of (T_{n} . T_{n}) has minimum internal path length with respect to all binary spanning trees of (H_{n}). Finally, each subtree of (T_{n}) is contained in the optimal sized subcube of (H_{n}). This collection of almost complete binary trees is important for the implementation of tree-structured computation on hypercube configured multiprocessors. 1994 Academic Press, Inc.