1. Embedding meshes into locally twisted cubes
- Author
-
Han, Yuejuan, Fan, Jianxi, Zhang, Shukui, Yang, Jiwen, and Qian, Peide
- Subjects
- *
PARALLEL computers , *COMPUTER systems , *COMPUTER science , *COMPUTER engineering , *COMPUTER networks , *NUMERICAL grid generation (Numerical analysis) , *OPERATOR theory , *CUBES - Abstract
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]
- Published
- 2010
- Full Text
- View/download PDF