Embedding a family of meshes into twisted cubes |
| |
Authors: | Chia-Jui Lai |
| |
Affiliation: | a Department of Finance and Banking, Dahan Institute of Technology, Hualien, Taiwan 970, R.O.C. b Department of Computer and Information Science, National Hualien University of Education, Hualien, Taiwan 970, R.O.C. |
| |
Abstract: | The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. The twisted cube is an important variation of the hypercube. Let TQn denote the n-dimensional twisted cube. In this paper, we consider embedding a family of 2-dimensional meshes into a twisted cube. The main results obtained in this paper are: (1) For any odd integer n?1, there exists a mesh of size 2×2n−1 that can be embedded in the TQn with unit dilation and unit expansion. (2) For any odd integer n?5, there exists a mesh of size 4×2n−2 that can be embedded in the TQn with dilation 2 and unit expansion. (3) For any odd integer n?5, a family of two disjoint meshes of size 4×2n−3 can be embedded into the TQn with unit dilation and unit expansion. Results (1) and (3) are optimal in the sense that the dilations and expansions of the embeddings are unit values. |
| |
Keywords: | Twisted cubes Mesh embedding Dilation Expansion Interconnection networks |
本文献已被 ScienceDirect 等数据库收录! |
|