Embedding a mesh of trees in the crossed cube

作者：Dong, Qiang^*; Zhou, Junlin; Fu, Yan; Yang, Xiaofan

来源：Information Processing Letters, 2012, 112(14-15): 599-603.

DOI：10.1016/j.ipl.2012.04.013

• Interconnection networks
• Graph embedding
• Crossed cube
• Mesh of trees
• Parallel computing

Crossed cubes are an important class of variants of hypercubes as interconnection topologies in parallel computing. In this paper, we study the embedding of a mesh of trees in the crossed cube. Let n be a multiple of 4 and N = 2((n-2)/2). We prove that an N x N mesh of trees (containing 3N(2) - 2N nodes) can be embedded in an n-dimensional crossed cube (containing 4N(2) nodes) with dilation 1 and expansion about 4/3. This result shows that crossed cubes are promising interconnection networks since mesh of trees enables fast parallel computation.

• 出版日期2012-8-15
• 单位电子科技大学; 重庆大学