National Chiao Tung University
Hsinchu, Taiwan, R.O.C.
The hypercube is a good host graph into which other structures such as arrays, rings and binary trees can be embedded. It has been shown that a complete binary tree of level h+1, Th+1 with 2h+1-1 nodes, can be embedded into an h-dimensional hypercube with dilation 2, congestion 2 and load 3. This paper presents an optimal algorithm that embeds Th into an n-dimensional hypercube (h>n*1) with dilation 2, congestion 2 and load 2h-n.
Keywords: embedding, complete binary tree, hypercube
Received April 8, 1995; revised September 24, 1995.
Communicated by Shing-Tsaan Huang.
*Supported by National Science Council of R.O.C. under grant NSC85-2213-E009-052.