Multiple Network Embeddings into Hypercubes
Title | Multiple Network Embeddings into Hypercubes |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Gupta, A., & Hambrusch S. E. |
Other Numbers | 519 |
Abstract | In this paper we study the problem of how to efficiently embed r interconnection networks G(subscript 0),...G(subscript r-1), r is less than or equal to k, into a k-dimensional hypercube H so that every node of the hypercube is assigned at most r nodes all of which belong to different G(subscript i)s. When each G(subscript i) is a complete binary tree or a leap tree of 2(superscript k)-1 nodes, we describe an embedding achieving a dilation of 2 and a load of 5 and 6, respectively. For the cases when each G(subscript i) is a linear array of a 2-dimensional mesh of 2(superscript k) nodes, we describe embeddings that achieve a dilation of 1 and an optimal load of 2 and 4, respectively. Using these embeddings, we also show that r(subscript 1) complete binary trees, r(subscript 2) leap trees, r(subscript 3) linear arrays, and r(subscript 4) meshes can simultaneously be embedded into H with constant dilation and load, (4 over sum over i=1) (r(subscript i)) is less than or equal to k. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-89-20.pdf |
Bibliographic Notes | ICSI Technical Report TR-89-020 |
Abbreviated Authors | Ajay Gupta and S. E. Hambrusch |
ICSI Publication Type | Technical Report |