Optimal algorithms of node-to-node fault tolerant routing in (n,k)-star graph

It is important for an interconnection network to route data among nodes if there are fault nodes in the network. Alternative paths in case of node failures can not only avoid communication bottlenecks, but increase the efficiency of message transmission In this paper we give an algorithm which, given at most n-2 faulty nodes s and t in the (n,k)-star graph S-n,S-k, finds a fault-free path s -> t of length at most D(S-n-1,S-k-1)+6 in O(n) time, where D(S-n-1,S-k-1) is the diameter of S-n-1,S-k-1. Using this algorithm as a subroutine we present another algorithm, given at most n-1 faulty nodes such that the result graph is also connected, finds a fault-free path s -> t of length at most D(S-n-1,S-k-1)+8 in O(n) time. The algorithms are optimal in the sense that both the upper bounds in the length of s -> t and the time complexity are optimal.