FAULT-TOLERANT EMBEDDING MULTIPLE COMPLETE BINARY-TREES INTO HYPERCUBES

This paper presents some fault-tolerant embedding algorithms to map mu ltiple complete binary trees (CBTs) into hypercubes. With dilation 1 a nd 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 ex pansion, 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 tolerat ing any two faulty nodes having dilation 1 and expansion 4/3. Furtherm ore, 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.