Advanced fault tolerant routing in hypercubes

We study the fault tolerant properties of n-dimensional hypercubes H_n for node-to-set and set-to-set routing problems on a general fault tolerant routing model, cluster fault tolerant routing, which is a natural extension of the well studied node fault tolerant routing. A cluster of a graph G is a connected subgraph of G and a cluster is called faulty if all nodes in the cluster are faulty. For node-to-set routing and set-to-set routing, where k(2⩽k⩽n) fault free node disjoint paths are needed, in H_n, we show that the maximum numbers of fault clusters of diameter at most 1 that can be tolerated is n-k. We give O(kn) optimal time algorithms which find k fault free node disjoint paths of length at most n+3 for node-to-set and k fault free node disjoint paths of length at most 2n for set-to-set cluster fault tolerant routing problems in H_n, respectively. We also prove that n+2 is an optimal upper bound on the length of the routing paths for node-to-set cluster fault tolerant routing