A fast fault-identification algorithm for bijective connection graphs using the PMC model |
| |
| Authors: | Tseng-Kuei Li Chang-Hsiung Tsai Hong-Chun Hsu |
| |
| Affiliation: | 1. Department of Computer Science and Information Engineering, Ching Yun University, JungLi 320, Taiwan, ROC;2. Department of Computer Science and Information Engineering, National Dong Hwa University, Hualien 970, Taiwan, ROC;3. Department of Medical Informatics, Tzu Chi University, Hualien 970, Taiwan, ROC;1. School of Mathematics and Computer Science, Fujian Normal University, Fuzhou, Fujian, 350007, PR China;2. Fujian Provincial Key Laboratory of Network Security and Cryptology (Fujian Normal University), Fujian Normal University, Fuzhou, Fujian, 350108, PR China;3. Department of Computer Science, Montclair State University, Upper Montclair, NJ 07043, USA;1. Key Laboratory of Intelligent Computing & Information Processing of Ministry of Education, School of Mathematics, Xiangtan University, Xiangtan, Hunan, 411105, China;2. School of Mathematical Sciences, Beijing Normal University, Laboratory of Mathematics and Complex Systems, Ministry of Education, Beijing, 100875, China;1. Department of Computer Science and Information Engineering, Hungkuang University, Taichung City 433, Taiwan, ROC;2. School of Computer Science and Technology, Soochow University, Suzhou 215006, China;1. College of Mathematics and Informatics, Fujian Normal University, Fuzhou, Fujian 350117 PR China;2. Center for Applied Mathematics of Fujian Province (Fujian Normal University), Fuzhou, Fujian 350117 PR China;3. Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, USA |
| |
| Abstract: | 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 Möbius 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 Dahura–Masson’s algorithm when applied to BC graphs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
