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

fYear

1994

fDate

22-26 Aug 1994

Firstpage

182

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/TENCON.1994.369312

Filename

369312