K. Kaneko, N. Sawada, and S. Peng (Japan)
Cluster Faults, Routing Algorithm, Polynomial Algorithm, Dependability, Interconnection Network
In this paper, we propose an O(n) algorithm that finds a fault-free path between any pair of non-faulty nodes in an n-pancake graph with n−2 faulty clusters whose diameters are at most 2. The lengths of the paths obtained by our algo rithm are at most d◦ (Pn)+7 where d◦ (Pn) = 5(n+1)/3 represents the upper bound of the diameter of Pn given by Gates and Papadimitriou. According to the computer experiment, the average time complexity of the algorithm turned out to be about O(n1.0 ).
Important Links:
Go Back
