Determining the Diagnosability of (1,2)-Matching Composition Networks and Its Applications

作者：Lee Chia Wei^*; Hsieh Sun Yuan

来源：IEEE Transactions on Dependable and Secure Computing, 2011, 8(3): 353-362.

DOI：10.1109/TDSC.2010.22

• PMC model
• diagnosability
• graph theory
• (1,2)-matching composition networks
• multiprocessor systems

The classic problem of determining the diagnosability of a given network has been studied extensively. Under the PMC model, this paper addresses the problem of determining the diagnosability of a class of networks called (1,2)-Matching Composition Networks, each of which is constructed by connecting two graphs via one or two perfect matchings. By applying our results to multiprocessor systems, we can determine the diagnosability of hypercubes, twisted cubes, locally twisted cubes, generalized twisted cubes, recursive circulants G(2(n),4) for odd n, folded hypercubes, augmented cubes, crossed cubes, Mobius cubes, and hyper-Petersen networks, all of which belong to the class of (1,2)-matching composition networks.

• 出版日期2011-6