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 等数据库收录! |
|