A novel algorithm to embed a multi-dimensional torus into a locally twisted cube

作者：Li Tseng Kui; Lai Chia Jui; Tsai Chang Hsiung^*

来源：Theoretical Computer Science, 2011, 412(22): 2418-2424.

DOI：10.1016/j.tcs.2011.01.035

• Interconnection networks
• Reflected link label sequence
• Torus embedding
• Mesh embedding
• Locally twisted cubes

This paper addresses how to embed a multi-dimensional torus of maximal size of into an n-dimensional locally twisted cube. The major contribution of this paper is that, for n >= 4, every k-dimensional torus of size 2(s1) x 2(s2) x ... x 2(sk) satisfying Sigma(k)(i=1) s(i) = n can be embedded into an n-dimensional locally twisted cube with dilation 2 and unit expansion. Further, an embedding algorithm can be constructed based on our embedding method, and the time complexity of this algorithm is linear with respect to the size of the locally twisted cube. The embedding is optimal in the sense that it has unit expansion.

• 出版日期2011-5-13
• 单位东华大学