SET-TO-SET FAULT-TOLERANT ROUTING IN HYPERCUBES

In this paper, we give an algorithm which, given a set F of at most n- k faulty nodes, and two sets S={s(1),...,S-k} and T={t(1),...,t(k)}, 1 less than or equal to k less than or equal to n, of non-faulty nodes in n-dimensional hypercubes H-n, finds k fault-free node disjoint path s s(i)-->t(ji), where (j(l),...,j(k)) is a permutation of (l,...,k), o f length at most n+k in O(kn logk) time. The result of this paper impl ies that n disjoint paths of length at most 2n for set-to-set node dis joint path problem in H-n can be found in O (n(2) logn) time.