Abstract
In this paper, we study the node-to-node fault tolerant routing problem in the n-dimensional hypercube H_n based on the cluster fault tolerant model. For a graph G, a faulty cluster is a connected subgraph of G such that all its nodes are faulty. In cluster fault tolerant routing problems, how many faulty clusters and how large of those clusters can be tolerated are studied. It has been known that for the node-to-node routing, n-dimensional hypercube H_n can tolerate as many as n-1 faulty clusters of diameter at most 1 with at most 2n-3 faulty nodes in total. In this paper, we extend the above result to show the sufficient conditions on faulty clusters of arbitrary diameters that H_n can tolerate. We also give an algorithm which, given a set of faulty clusters satisfying the sufficient conditions and non-faulty nodes s and t in H_n, finds a fault-free path of length d(s,t) + O(log n) in O(n+|F|) optimal time, where |F| is the total number of faulty nodes.