嵌置樹形機器到超立方體

Embedding of Tree Machines into Hypercubes

本研究在擴展度值=1、負載值=1、膨脹值=2、擁塞值=2的條件下，提出一個嵌置樹形機器到不完全超立方體的方法，其結果優於文獻[14]中的擴展值=(2h+1+2h)/(2h+1+2h-2)。接著考慮在負載平衡的情況下如何嵌置大型樹形機器到超立方體中，本研究在膨脹值=1、擁塞值=2、負載值=2的條件下，證明樹形機器TMh (h³1)可以嵌置到超立方體Hh+1，也可以在膨脹值=1、擁塞值=3、負載值=2h-n+1+2h-n的條件下嵌置到超立方體Hn (h³n³1)，且能保持嵌置的良好負載平衡。

In this paper, we present that a tree machine can be embedded into incomplete hypercube with expansion 1, load 1, dilation 2 and congestion 2. This result is better than the expansion (2h+1+2h)/(2h+1+2h-2) in [14]. Then we consider how to embed a large tree machine into a hypercube for considering load-balance. We have shown that a tree machine TMh (h³1) can be embedded into a hypercube Hh+1 with dilation 1, congestion 2 and load 2, and a tree machine TMh can be embedded into Hn (h³n³1) with dilaton 1, congestion 3 and load 2h-n+1+2h-n. The load of these embeddings is well balanced.