JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]


Journal of Information Science and Engineering, Vol. 21 No. 1, pp. 195-207


Dynamic Reconfiguration of Complete Binary Trees in Faulty Hypercubes


Chui-Cheng Chen
Department of Information Management 
Southern Taiwan University of Technology 
Tainan, 710 Taiwan


    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 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 2h+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.


Keywords: reconfiguration, complete binary tree, hypercube, faulty node, embedding

  Retrieve PDF document (JISE_200501_10.pdf)