Multiple Network Embeddings into Hypercubes

TitleMultiple Network Embeddings into Hypercubes
Publication TypeTechnical Report
Year of Publication1989
AuthorsGupta, A., & Hambrusch S. E.
Other Numbers519

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.

Bibliographic Notes

ICSI Technical Report TR-89-020

Abbreviated Authors

Ajay Gupta and S. E. Hambrusch

ICSI Publication Type

Technical Report