Loading...
Please wait, while we are loading the content...
Similar Documents
Congestion-free, dilation-2 embedding of complete binary trees into star graphs.
| Content Provider | CiteSeerX |
|---|---|
| Author | Tseng, Yu-Chee Chen, Yuh-Shyan Juang, Tong-Ying Chang, Chiou-Jyu |
| Abstract | Trees are a common structure to represent the inter-task communication pattern of a parallel algorithm. In this paper, we consider the embedding a complete binary tree in a star graph with the objective of minimizing congestion and dilation. We develop two embeddings: i) a congestion-free, dilation-2, load-1 embedding of a level- p binary tree, and ii) a congestion-free, dilation-2, load-2 k embedding of a level-(p+k) binary tree, into an n-dimensional star graph, where p = \Sigma n i=2 blog ic = \Omega\Gamma n log n) and k is any positive integer. The first result offers a tree of size comparable or superior to existing results, but with less congestion and dilation. The second result provides more flexibility in the embeddable tree sizes compared to existing results. Keywords: Graph embedding, interconnection network, complete binary tree, star graph, parallel processing. This research was supported in part by the National Science Council, R.O.C., under grant numbers NS... |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Star Graph Complete Binary Tree Dilation-2 Embedding Second Result Positive Integer Parallel Algorithm Load-1 Embedding Parallel Processing Embeddable Tree Size Inter-task Communication Pattern N-dimensional Star Graph Interconnection Network Common Structure National Science Council Load-2 Embedding Binary Tree Grant Number Level Binary Tree Blog Ic Omega Gamma First Result |
| Content Type | Text |
