Optimal embeddings of multiple graphs into a hypermesh
Sook-Yeon Kim, Kyung‐Yong Chwa · 2002
A hypermesh, a versatile parallel architecture, is obtained from a 2-dimensional mesh by replacing each linear connection with a hyper-edge. We optimally embed multiple graphs into a hypermesh by a labeling strategy. This optimal embedding provides an optimal expansion, dilation and congestion at the same time. First, we label on an N-node graph G, possibly disconnected, such that this labeling makes it possible to optimally embed multiple copies of G into an N'/spl times/N' hypermesh when N' is divisible by N. Second, we show that many important classes of graphs have this labeling: for example, tree, cycle, mesh of trees and product graphs including mesh, torus, and hypercube. Third, we generalize these results to optimally embed multiple graphs into a multidimensional and possibly non-square hypermesh. This labeling strategy is applicable to the embeddings of other classes of graphs into a hypermesh.