DocumentCode
2978987
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
fYear
1999
fDate
1999
Firstpage
80
Lastpage
85
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Architectures, Algorithms, and Networks, 1999. (I-SPAN '99) Proceedings. Fourth InternationalSymposium on
Conference_Location
Perth/Fremantle, WA
ISSN
1087-4089
Print_ISBN
0-7695-0231-8
Type
conf
DOI
10.1109/ISPAN.1999.778921
Filename
778921
Link To Document