A fast fault-identification algorithm for bijective connection graphs using the PMC model ?
Diagnosis of reliability is an important topic for interconnection networks. Under the classical PMC model, Dahura and Masson [5] proposed a polynomial time algorithm with time complexity O(N2.5) to identify all faulty nodes in an N-node network. This paper addresses the fault diagnosis of so called bijective connection (BC) graphs including hypercubes, twisted cubes, locally twisted cubes, crossed cubes, and Mbius cubes. Utilizing a helpful structure proposed by Hsu and Tan [20] that was called the extending star by Lin et al. [24], and noting the existence of a structured Hamiltonian path within any BC graph, we present a fast diagnostic algorithm to identify all faulty nodes in O(N) time, where N=2n, n?4, stands for the total number of nodes in the n-dimensional BC graph. As a result, this algorithm is significantly superior to DahuraMassons algorithm when applied to BC graphs.
pmc model reliability interconnection network diagnostic algorithm diagnosability