Embedding a family of meshes into twisted cubes

作者：Lai Chia Jui; Tsai Chang Hsiung^*

来源：Information Processing Letters, 2008, 108(5): 326-330.

DOI：10.1016/j.ipl.2008.06.005

• Twisted cubes
• Mesh embedding
• Dilation
• Expansion
• Interconnection networks

The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. The twisted cube is all important variation of the hypercube. Let TQ(n) 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 x 2(n-1) that can be embedded in the TQ(n) with unit dilation and unit expansion. (2) For any odd integer n >= 5, there exists a mesh of size 4 x 2(n-2) that can be embedded in the TQ(n) with dilation 2 and unit expansion. (3) For any odd integer n >= 5, a family of two disjoint meshes of size 4 x 2(n-3) can be embedded into the TQ(n) 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.

• 出版日期2008-11-15