EMBEDDING AND RECONFIGURATION OF BINARY-TREES IN FAULTY HYPERCUBES

We consider the problem of embedding and reconfiguring binary tree str uctures in faulty hypercubes. We assume that the number of faulty node s is at most (n - 2), where n is the number of dimensions of the hyper cube; we further assume that the location of faulty nodes are known. O ur embedding techniques are based on a key concept called free dimensi on, which can be used to partition a cube into subcubes such that each subcube contains at most one faulty node. Using this approach, two di stributed schemes are provided for embedding and reconfiguration in fa ulty hypercubes. We extend the free dimension concept to degree oi occ upancy and use this to develop a distributed scheme for reconfiguratio n of binary tree in faulty hypercubes with up to [3n/2] node faults.