Dynamic embeddings of trees and quasi-grids into hyper-de Bruijn networks
Sabine R. Öhring, Sajal Kumar Das · 2002
This paper deals with optimal embeddings of various topologies into the hyper-de Bruijn network, which is a combination of the well known hypercube and the de Bruijn graph. In particular, the authors develop modular embeddings of complete binary trees and other tree-related graphs, and dynamic task allocation embeddings of dynamically evolving arbitrary binary trees. Additionally, an optimal embedding of butterflies and a subgraph-embedding of cube-connected cycles are presented. They also consider how to dynamically embed dynamically evolving grid-structures (so called quasi-grids) into hyper-de Bruijn networks. The results are important in mapping data and algorithm structures on multiprocessor networks.>