Embedding of complete binary tree with 2-expansion in a faulty Flexible Hypercube

Although the embedding of complete binary trees in faulty hypercubes has re ceived considerable attention, to our knowledge, no paper has demonstrated how to embed a complete binary tree in a faulty Flexible Hypercube. Therefo re, this investigation presents an algorithm to facilitate the embedding jo b when the Flexible Hypercube contains faulty nodes. Of particular concern are the network structures of the Flexible Hypercube that balance the load before as well as after faults start to degrade the performance of the Flex ible Hypercube. Furthermore, to obtain the replaceable node of the faulty n ode, 2-expansion is permitted such that up to (n - 2) faults can be tolerat ed with congestion 1, dilation 4 and load 1. (C) 2001 Elsevier Science B.V. All rights reserved.