Title :
An optimal embedding of incomplete binary trees onto incomplete hypercubes
Author :
Huang, Chien-Hung ; Hsiao, Ju-Yuan ; Lee, R.C.T. ; Fang, Jywe-Fei
Author_Institution :
Dept. of Comput. Sci., Tsinghua Univ., Beijing, China
Abstract :
It has been proved that incomplete binary trees can not be embedded onto incomplete hypercubes with both expansion-1 and dilation-1. In this paper we propose an optimal embedding algorithm to embed this issue with expansion-1, dilation-2. Our algorithm is a linear time algorithm, which is optimal in terms of time complexity. Furthermore, the embedding scheme is as desirable to be simple such that the implementation is quite easy
Keywords :
computational complexity; hypercube networks; parallel architectures; trees (mathematics); embedding scheme; incomplete binary trees; incomplete hypercubes; linear time algorithm; optimal embedding; time complexity; Binary trees; Constraint optimization; Costs; Delay; Hypercubes; Labeling; Routing;
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 1999. (I-SPAN '99) Proceedings. Fourth InternationalSymposium on
Conference_Location :
Perth/Fremantle, WA
Print_ISBN :
0-7695-0231-8
DOI :
10.1109/ISPAN.1999.778921
