OPTIMAL-ALGORITHMS FOR NODE-TO-NODE FAULT-TOLERANT ROUTING IN HYPERCUBES

In this paper, we give an algorithm which, given at most n - 1 faulty nodes and non-faulty nodes s and t in the n-dimensional hypercube, H-n , finds a fault-free path s --> t of length at most d(s,t) + 2 in O(n) time, where d(s,t) is the distance between s and t in H-n. Using this algorithm as a subroutine, we present another algorithm which, given at most 2n - 3 faulty nodes such that the faulty nodes can be covered by n - 1 subgraphs of diameter 1, finds a fault-free path s --> t of l ength at most d(s,t) + 4 in O(n) time. The algorithms are optimal in t he sense that both the upper bounds on the length of s --> t and the t ime complexity are optimal.