AN EFFICIENT ALGORITHM FOR NODE-TO-NODE ROUTING IN HYPERCUBES WITH FAULTY CLUSTERS

In this paper, Ire study the node-to-node fault tolerant routing probl em in n-dimensional hypercubes H-n based on the cluster fault tolerant model For a graph G, a faulty cluster is a connected subgraph of G su ch that all its nodes are faulty. In cluster fault tolerant routing pr oblems, how many faulty clusters and how large those clusters can be t olerated are studied. It was proved that for node-to-node routing, H-n can tolerate as many as n - 1 faulty clusters of diameter at most 1 w ith at most 2n - 3 faulty nodes in total. In this paper, we give an al gorithm which, given at most n - 1 faulty clusters of diameter at most 1 with 2n - 3 faulty nodes in total and non-faulty nodes s and t in H -n, finds a fault-free path s --> t of length at most n + 2 in O(n) op timal time. The upper bound on the length of the path is optimal when the distance between s and t is n - 2.