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

Journal of Inforamtion Science and Engineering, Vol.12 No.2, pp.307-314 (June 1996)
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, 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.