Embedding a family of disjoint 3D meshes into a crossed cube |
| |
Authors: | Qiang Dong Juan Zhao |
| |
Affiliation: | a College of Computer Science, Chongqing University, Chongqing 400044, China b Department of Foreign Language, Aba Teachers College, Aba 623000, Sichuan, China c Department of Computer Science, Hong Kong Baptist University, Kowloon, Hong Kong |
| |
Abstract: | Crossed cubes are an important class of hypercube variants. This paper addresses how to embed a family of disjoint 3D meshes into a crossed cube. Two major contributions of this paper are: (1) for n?4, a family of two disjoint 3D meshes of size 2×2×2n-3 can be embedded in an n-D crossed cube with unit dilation and unit expansion, and (2) for n?6, a family of four disjoint 3D meshes of size 4×2×2n-5 can be embedded in an n-D crossed cube with unit dilation and unit expansion. These results mean that a family of two or four 3D-mesh-structured parallel algorithms can be executed on a same crossed cube efficiently and in parallel. Our work extends the results recently obtained by Fan and Jia J. Fan, X. Jia, Embedding meshes into crossed cubes, Information Sciences 177(15) (2007) 3151-3160]. |
| |
Keywords: | Interconnection network Crossed cube 3D mesh Graph embedding Dilation Expansion |
本文献已被 ScienceDirect 等数据库收录! |
|