Previous [ 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 (January 2005)

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

Full Text () Retrieve PDF document (200501_10.pdf)

Received May 27, 2002; revised July 14, 2003; accepted October 2, 2003.
Communicated by Hsu-Chun Yen.