| Embedding Tree-Related Graphs Into Hypercubes (1997) | |||||||||||||||||
Abstract | |||||||||||||||||
| We propose a general strategy of many-to-one embedding of treerelated graphs into hypercubes. These tree-related graphs include complete binary tree (CBT), mesh of trees (MOT), pyramid and so on. This strategy evenly distributes the same level nodes of a tree-related graph to the nodes of a hypercube. This distribution is a great advantage because the same level nodes are always activated simultaneously in most algorithms of tree-related structure. Using this strategy, we design several embedding methods that are more cost effective than those in previous work. These methods provide minimal or near minimal values in the embedding measures, such as dilation, load factor and congestion. Concerning CBTs, we design two methods: one with the minimal dilation and the other with the minimal load factor. The congestion of both methods is minimal. In addition, we also show that both the dilation and load factor cannot be simultaneously minimized when the same level nodes of the CBT are evenly ... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||