LINEAR-TIME ALGORITHMS FOR FAULT-TOLERANT ROUTING IN HYPERCUBES AND STAR GRAPHS

In this paper, we study the following node-to-node fault tolerant rout ing problem: In the presence of up to n-1 faulty nodes, find a fault-f ree path which connects any two non-faulty nodes s and t in an n-conne cted graph. For node-to-node fault tolerant routing in n-dimensional h ypercubes H-n, we give an algorithm which finds a fault-free path s -- > t of length at most d(s,t) + 2[log n/d(s,t)] in O(n) time, where d(s ,t) is the distance between s and t. We also show that a fault-free pa th s --> t in Hn of length at most d(s,t) + 2i, less than or equal to i < [log n/d(s,t)], can be found in O(d(s,t)n/2(i-1) + n) time. For no de-to-node fault tolerant routing in n-dimensional star graphs G(n), w e give an algorithm which finds a fault-free path s --> t of length at most min{d(G(n))+3, d(s,t)+6} in O(n) time, where d(G(n)) = [3(n-1)/2 ] is the diameter of G(n). It is previously known that, in H-n, a faul t-free path s --> t of length at most d(s,t) for d(s,t) = n and at mos t d(s,t) + 2 for d(s,t) < n can be found in O(d(s,t)n) time, and in G( n), a fault-free path s --> of length at most min{d(G(n))+1, d(s,t)+4} can be found in O(d(s,t)n) time. When the time efficiency of finding the routing path is more important than the length of the path, the al gorithm in this paper are better than the previous ones.