Previous | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] |

Optimal Embedding of Large Complete Binary

Trees into Hypercubes

*Department of Computer Science and Information Engineering
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, T_{h+1} with 2^{h+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 T_{h }into an n-dimensional hypercube (h>n*1) with dilation 2, congestion 2 and load 2^{h-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.