Reconfiguting binary tree structures ina faulty supercube with unbounded expansion

[[abstract]]The supercube is a generalization of interconnection network that is derived from the hypercube. Unlike the hypercube, the supercube can be constructed for any number of nodes. That is, the supercube is incrementally expandable. In addition, the supercube retains the connectivity and diameter properties of the corresponding hypercube. In this paper, the problem of embedding and reconfiguring complete binary tree structures is considered in a supercube with faulty nodes. There are two embedding algorithms proposed in this paper. The first embedding algorithm allows 2-expansion such that the result can be tolerated up to (n−2) faults with congestion 1 and dilation 4 where (n−1) is the dimension of a supercube. The second result enables us to obtain the good embedding of a complete binary tree into a faulty supercube with unbounded expansion such that up to O(n2−m2) faults can be tolerated with congestion 1 and dilation 4 where (n−1) is the dimension of a supercube and (m−1) is the height of a complete binary tree