Efficient distributed schemes for embedding binary trees into incomplete hypercubes
Yao‐Ming Yeh, Yiu-Cheng Shyu · 2002
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.>