应用数学进展  >> Vol. 5 No. 4 (November 2016)

扩张3元n立方的1好邻诊断度
The 1-Good-Neighbor Diagnosability of Augmented 3-Ary n-Cubes

DOI: 10.12677/AAM.2016.54087, PDF, HTML, XML, 下载: 1,146  浏览: 1,349 

作者: 赵楠:河南师范大学数学与信息科学学院,河南 新乡;王世英*:河南师范大学数学与信息科学学院,河南 新乡;河南师范大学,河南省大数据统计分析与优化控制工程实验室,河南 新乡

关键词: 互连网络扩张3元n立方连通度诊断度Interconnection Network Augmented 3-Ary n-Cubes Connectivity Diagnosability

摘要: 多重处理器系统的故障诊断是一个非常重要的研究课题。处理器系统的g好邻诊断度是在2012年被Peng等提出来的,它要求每个非故障顶点至少有g个非故障邻点。扩张3元n立方体是一个受欢迎的拓扑结构,它有许多好的性质。在本文中,我们证明了扩张3元n立方体在PMC模型和MM*模型下的1好邻诊断度都是8n-10(n≥4)
Abstract: Diagnosability of a multiprocessor system is an important study topic. The g-good-neighbor diag-nosability of the system was proposed by Peng et al. in 2012, which restrained every fault-free node containing at least g fault-free neighbors. As a favorable topology structure, the augmented 3-ary n-cubes graph has many good properties. In this paper, we prove that the 1-good-neighbor diagnosability of augmented 3-ary n-cube is 8n-10 under the PMC model and MM* model for n≥4.

文章引用: 赵楠, 王世英. 扩张3元n立方的1好邻诊断度[J]. 应用数学进展, 2016, 5(4): 754-761. http://dx.doi.org/10.12677/AAM.2016.54087

参考文献

[1] Preparata, F., Metze, G. and Chien, R.T. (1968) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Electronic Computers, 12, 848-854.
[2] Joon, M. and Miroslaw, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, Portland, June 1981, Vol. 11, 173-175.
[3] Lai, P.-L., Tan, J.J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175.
https://doi.org/10.1109/TC.2005.19
[4] Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under the PMC Model. Applied Mathematics and Computation, 218, 10406-10412.
https://doi.org/10.1016/j.amc.2012.03.092
[5] Yuan, J., Liu, A.X., Ma, X., Liu, X.L., Qin, X. and Zhang, J.F. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Ary n-Cubes under the PMC Model and MM* Model. IEEE Transactions on Pa-rallel and Distributed Systems, 26, 1165-1177.
https://doi.org/10.1109/TPDS.2014.2318305
[6] Yuan, J., Liu, A.X., Qin, X., Li, J. and Zhang, J.F. (2016) The g-Good-Neighbor Conditional Diagnosability of 3-Ary n-Cubes under the PMC Model and MM* Model. Theoretical Computer Science, 622, 144-162.
[7] Wang, M., Lin, Y.Q. and Wang, S.Y. (2016) The 2-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. Theoretical Computer Science, 628, 92-100.
https://doi.org/10.1016/j.tcs.2016.03.019
[8] Wang, M., Guo, Y.B. and Wang, S.Y. (2015) The 1-Good-Neighbor Diagnosa-bility of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. International Journal of Computer Mathematics, 1-12.
https://doi.org/10.1080/00207160.2015.1119817
[9] Wang, S.Y. and Han, W.P. (2016) The g-Good-Neighbor Conditional Diagnosability of n-Dimentional Hypercubes under the PMC Model and MM* Model. International Processing Letters, 116, 574-577.
https://doi.org/10.1016/j.ipl.2016.04.005
[10] Xiang, Y.L. and Stewart, L.A. (2011) Augmented k-Ary n-Cubes. Information Science, 181, 239-256.
https://doi.org/10.1016/j.ins.2010.09.005
[11] Lin, R.Z. and Zhang, H.P. (2015) The Restricted Edge-Connectivity and Restricted Connectivity of Augmented k-Ary n-Cubes. International Journal of Computer Mathematics, 93, 1281-1298.
https://doi.org/10.1080/00207160.2015.1067690
[12] Dahbura, A.T. and Masson, G.M. (1984) An Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492.
https://doi.org/10.1109/TC.1984.1676472