Dynamic reconfiguration of complete binary trees in faulty hypercubes
In this paper, we present a method for reconfiguring dynamically a complete binary tree in faulty hypercubes. First, we use a dynamic algorithm to reconfigure a complete binary tree of height h (h greater than or equal to 0) in an (h greater than or equal to 1)-dimensional faulty hypercube. If there is a faulty node in the hypercube, both the dilation and congestion values are 2 after reconfiguration. If there are two faulty nodes in the hypercube, both the dilation and congestion values are 3 after reconfiguration. If there are more than two faulty nodes in the hypercube, we impose a constraint on the faulty node type, and both the dilation and congestion values are 3 after reconfiguration. Then we reconfigure a complete binary tree of height h in an (h + 2)-dimensional hypercube with at most 2(h+1) - 1 nodes, and the dilation and congestion values are, respectively, 2 and 1 after reconfiguration. The number of affected nodes is minimized following reconfiguration.
reconfiguration complete binary tree hypercube faulty node embedding