Title :
Efficient distributed schemes for embedding binary trees into incomplete hypercubes
Author :
Yeh, Yao-Ming ; Shyu, Yiu-Cheng
Author_Institution :
Dept. of Inf. & Comput. Educ., Nat. Taiwan Normal Univ., Taipei, Taiwan
Abstract :
Presents two fundamental schemes to embed four types of tree topologies (complete binary trees, two-rooted complete binary trees, Fibonacci search binary trees and incomplete binary trees) into incomplete hypercubes with a dilation of 1. Our results show that the embeddings in incomplete hypercubes can lead to better processor utilization as compared to those obtained in complete hypercubes. Moreover, all proposed schemes are executed in a distributed fashion with a time complexity O(log N), where N is the total number of tree nodes. These schemes have a superior time performance compared with previous schemes
Keywords :
computational complexity; distributed algorithms; hypercube networks; network topology; trees (mathematics); Fibonacci search binary trees; binary tree embedding; dilation; distributed schemes; incomplete binary trees; incomplete hypercubes; performance; processor utilization; time complexity; tree nodes; tree topologies; two-rooted complete binary trees; Binary trees; Computer science education; Costs; Councils; Distributed algorithms; Embedded computing; Hypercubes; Multiprocessing systems; Topology;
Conference_Titel :
TENCON '94. IEEE Region 10's Ninth Annual International Conference. Theme: Frontiers of Computer Technology. Proceedings of 1994
Print_ISBN :
0-7803-1862-5
DOI :
10.1109/TENCON.1994.369312
