EMBEDDING STAR NETWORKS INTO HYPERCUBES

The star interconnection network has recently been suggested as an alt ernative to the hypercube. As hypercubes are often viewed as universal and capable of simulating other architectures efficiently, we investi gate embeddings of star network into hypercubes. Ourt embeddings exhib it a marked trade-off between dilation and expansion. For the n-dimens ional star network we exhibit: 1) a dialtion N-1 embedding of S-n into H-N, where N = [log(2)(n!)], 2) a dilation 2(d + 1) embedding of S-n into H-2d+n-1, where d = [log(2)([n/2]!)], 3) a dilation 2d + 2i embed ding of S-2'm into H-2'd+i2'm-2i+1, where d = [log(2)(m!)], 4) a dilat ion L embedding of S-n into H-d, where L = 1 + [log(2)(n!)], and d = ( n-1)L, 5) a dilation (k + 1)(k + 2)/2 embedding of S-n into H-n(k+1-2k +1+1), where k = [log(2)(n - 1)], 6) a dilation 3 embedding of S-2k+1 into H-2k3+k, and 7) a dilation 4 embedding of S-3k+2 into H-?(3k2+3k1+ Some of the embeddings are, in fact, optimum, in both dilation and expansion for small values of n. We also show that the embedding of S- n into its optimum hypercube requires dilation Omega(log(2) n).