Optimal Algorithms for Node-to-Node Fault Tolerant Routing in Hypercubes
Q.-P. Gu · The Computer Journal · 1996
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, Hn, 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 Hn. 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.