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 length at most d(s,t) + 4 in O(n) time. The algorithms are optimal in the sense that both the upper bounds on the length of s --> t and the time complexity are optimal.