Node-to-set and set-to-set cluster fault tolerant routing in hypercubes

We study node-to-set and set-to-set fault tolerant routing problems in n-dimensional hypercubes H-n. Node-to-set routing problem is that given a node s and a set of nodes T = {t(1),..., t(k)}, finds k node-disjoint paths s --> t(i), 1 less than or equal to i less than or equal to k. Set-to-set routing problem is that given two sets of nodes S = {s(1),...,s(k)} and T = {t(1),..., t(k)}, finds k node-disjoint paths, each path connects a node of S and a node of T. From Menger's theorem, it is known that these two problems in H-n can tolerate at most n - k arbitrary faulty nodes. In this paper, we prove that both routing problems can tolerate n - k arbitrary faulty subgraphs (called cluster) of diameter 1. For 2 less than or equal to k less than or equal to n, we show that, in the presence of at most n - k faulty clusters of diameter at most i, the k paths of length at most n + 2 for node-to-set routing in H-n can be found in O(kn) optimal time and the k paths of length at most n + k + 2 for set-to-set routing in H-n can be found in O(kn log k) time. The upper bound n + 2 on the length of the paths for node-to-set routing in H-n is optimal. (C) 1998 Elsevier Science B.V. All rights reserved.