Dynamic Reconfiguration of Complete Binary Trees in Faulty Hypercubes
Chui-Cheng Chen · 2005
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 ≥ 0) in an (h + 1)-dimensional faulty hypercube. If there is a faulty node in the hypercube, both the dilation and congestion values are 2 after recon-figuration. If there are two faulty nodes in the hypercube, both the dilation and conges-tion values are 3 after reconfiguration. If there are more than two faulty nodes in the hy-percube, we impose a constraint on the faulty node type, and both the dilation and con-gestion values are 3 after reconfiguration. Then we reconfigure a complete binary tree of height h in an (h + 2)-dimensional hypercube with at most 2h+1 − 1 nodes, and the dila-tion and congestion values are, respectively, 2 and 1 after reconfiguration. The number of affected nodes is minimized following reconfiguration.