An approach for torus embedding
Sook-Yeon Kim, Jeen Hur · 2003
We propose a new approach to embed a given torus G into another given torus H. The approach is applicable to tori of arbitrary dimension and size. We also analyze the costs of embedding in terms of load, dilation and congestion. In the case that G and H are rings, the load is optimal and the congestion is one. In the case that G and H are multi-dimensional square tori, the embedding costs are as follows: the load is asymptotically optimal; the dilation (congestion) is one if the torus G has equal or greater (less, respectively) number of nodes than that of H. In addition, we show that the approach induces efficient simulation of parallel algorithms.