Embedding a family of disjoint multi-dimensional meshes into a crossed cube

作者：Dong Qiang^*; Yang Xiaofan; Zhao Juan

来源：Information Processing Letters, 2008, 108(6): 394-397.

DOI：10.1016/j.ipl.2008.07.013

• Interconnection networks
• Crossed cube
• Multi-dimensional mesh
• Graph embedding

Crossed cubes are an important class of hypercube variants. This paper addresses how to embed a family of disjoint multi-dimensional meshes into a crossed cube. We prove that for n >= 4 and 1 <= m <= [n/2] - 1, a family of 2(m) disjoint k-dimensional meshes of size 2(t1) x 2(t2) x ... x 2(tk) each can be embedded in an n-dimensional crossed cube with unit dilation, where Sigma(k)(i=1) t(i) = n - m and max(1 <= i <= k){t(i)} >= n - 2m -1 . This result means that dilation, where I:k a family of mesh-structured parallel algorithms can be executed oil a same crossed cube efficiently and in parallel. Our work extends some recently obtained results.

• 出版日期2008-11-30
• 单位重庆大学; 南宁师范大学