Embedding meshes into locally twisted cubes

作者：Han, Yuejuan; Fan, Jianxi^*; Zhang, Shukui; Yang, Jiwen; Qian, Peide

来源：Information Sciences, 2010, 180(19): 3794-3805.

DOI：10.1016/j.ins.2010.06.001

• Locally twisted cube
• Mesh
• Embedding
• Dilation
• Expansion
• Parallel computing system

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQ(n)(V,E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n >= 1, a 2 x 2(n-1) mesh can be embedded in LTQ(n) with dilation 1 and expansion 1. (2) For any integer n >= 4, two node-disjoint 4 x 2(n-3) meshes can be embedded in LTQ(n) with dilation 1 and expansion 2. (3) For any integer n >= 3, a 4 x (2(n-2) - 1) mesh can be embedded in LTQ(n) with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2 x 2(n-1) mesh is also optimal in terms of expansion. We also present the analysis of 2p x 2q mesh embedding in locally twisted cubes.

• 出版日期2010-10-1
• 单位苏州大学