ALGORITHMS AND BOUNDS FOR SHORTEST PATHS AND DIAMETER IN FAULTY HYPERCUBES

In an n-dimensional hypercube Q(n), with the fault set Absolute value of F < 2n-2, assuming S and D are not isolated, we show that there exists a path of length equal to at most their Hamming distance plus 4. An algorithm with complexity O(Absolute value of F log n) is given to find such a path. Further, we obtain a bound for the diameter of the faulty hypercube Q(n) - F, when Absolute value of F < 2n - 2, as n + 2. This improves the previously known bound of n + 6 by Esfahanian [1]. Worst case scenarios are constructed to show that these bounds for shortest paths and diameter arc tight. We also show that when Absolute value of F < 2n - 2, the diameter bound is reduced to n + 1 if every node has at least 2 nonfaulty neighbors, and reduced to n if every node has at least 3 nonfaulty neighbors.