FAULT-TOLERANT EMBEDDING MULTIPLE COMPLETE BINARY-TREES INTO HYPERCUBES

This paper presents some fault-tolerant embedding algorithms to map multiple complete binary trees (CBTs) into hypercubes. With dilation 1 and the expansion 1, we first present an embedding algorithm to map two CBTs with height n-1, (n-1)-CBTs, into an n-dimensional hypercube, H-n tolerating two connected faulty nodes. With the same dilation and expansion, we then present an algorithm to map one (n-1)-CBT and two (n-2)-CBTs into H-n tolerating three connected faulty nodes. In addition, it is shown to embed one (n-1)-CBT and one (n-2)-CBT into H-n tolerating any two faulty nodes having dilation 1 and expansion 4/3. Furthermore, based on the subcube concept, our fault tolerant embedding scheme can be used to map multiple smaller CBTs into a hypercube tolerating multiple faulty nodes.