SET-TO-SET FAULT-TOLERANT ROUTING IN STAR GRAPHS

In this paper, we give an algorithm which, given a set F of at most (n - 1) - 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 - 1, of non-faulty nodes in n-dimensional star graphs G(n), finds k fault-free node disjoint paths s(i) --> t(ji), where (j(i),...,j(k)) is a permut ation of (1,...,k), of length at most d(G(n)) + 5 in O(kn) optimal tim e, where d(G(n)) = [3(n-1)/2] is the diameter of G(n).