Embedding meshes in hypercubes with edge faults

Abstract

Embedding meshes in hypercubes has been studied extensively. Most earlier works on embedding in faulty hypercubes considered edge failures as node failures. In this paper, we present results on embedding meshes in hypercubes with edge faults. Due to the high connectivity of hypercubes, meshes and tori could be embedded even in the presence of a large number of edge faults. We establish bounds on the number of such edge faults under which a mesh or torus can always be embedded. We also present a construction mechanism for such an embedding.

Keywords:

• Fault-tolerance
• embedding
• mesh
• hypercube

C.R. Categories:

• C 1.2
• B2.3

^*Corresponding author.

^*Corresponding author.

Notes

^*Corresponding author.