Embedding meshes/tori in faulty crossed cubes

The crossed cube is an important variant of the hypercube which is the most popular interconnection network for parallel processing. This paper is concerned with the problem of embedding meshes/tori in faulty crossed cubes. We reduce this mesh/tori embedding problem to the problem of embedding paths/cycles in faulty crossed cubes. Then, by exploiting the fault-tolerant pancyclicity of crossed cubes of lower dimension, several schemes for embedding 2D or 3D meshes/tori in faulty crossed cubes are proposed. All of these embeddings have small dilations and small congestions. The obtained results show that the parallel algorithms with mesh/torus task graphs can be efficiently executed on faulty crossed cubes. (C) 2010 Elsevier B.V. All rights reserved.