JISE


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


Journal of Information Science and Engineering, Vol. 12 No. 2, pp. 307-314


Optimal Embedding of Large Complete Binary Trees into Hypercubes


Chui-Cheng Chen and Rong-Jaye Chen

 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 Tinto an n-dimensional hypercube (h>n*1) with dilation 2, congestion 2 and load 2h-n.


Keywords: embedding, complete binary tree, hypercube

  Retrieve PDF document (JISE_199602_08.pdf)