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 giv en a node s and a set of nodes T = {t(1),..., t(k)}, finds k node-disj oint 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, ea ch path connects a node of S and a node of T. From Menger's theorem, i t is known that these two problems in H-n can tolerate at most n - k a rbitrary faulty nodes. In this paper, we prove that both routing probl ems 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 diamete r at most i, the k paths of length at most n + 2 for node-to-set routi ng 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.