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

¡@

in Faulty Hypercubes

**Chui-Cheng Chen**

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 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.

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

Retrieve PDF document (**200501_10.pdf**)

Received May 27, 2002; revised July 14, 2003; accepted October 2, 2003.

Communicated by Hsu-Chun Yen.