Embedding meshes into locally twisted cubes

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. (C) 2010 Elsevier Inc. All rights reserved.