Search

Abstract: 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×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×2 n−3 meshes can be embedded in LTQ n with dilation 1 and expansion 2. (3) For any integer n ⩾3, a 4 ×(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×2 n−1 mesh is also optimal in terms of expansion. We also present the analysis of 2p ×2q mesh embedding in locally twisted cubes. [Copyright &y& Elsevier]