Algorithms and bounds for shortest paths and diameter in faultyhypercubes |
| |
Authors: | Tien S-B Raghavendra CS |
| |
Affiliation: | Dept. of Electr. Eng., Southern Illinois Univ., Carbondale, IL; |
| |
Abstract: | In an n-dimensional hypercube Qn, with the fault set |F|<2n-2, assuming S and D are not isolated, it is shown that there exists a path of length equal to at most their Hamming distance plus 4. An algorithm with complexity O (|F|logn) is given to find such a path. A bound for the diameter of the faulty hypercube Qn-F, when |F|<2n-2, as n+2 is obtained. This improves the previously known bound of n+6 obtained by A.-H. Esfahanian (1989). Worst case scenarios are constructed to show that these bounds for shortest paths and diameter are tight. It is also shown that when |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 |
| |
Keywords: | |
|
|