Mo¨bius立方体的1好邻连通度和诊断度
The 1-Good-Neighbor Connectivity and Diagnosability of Mo¨bius Cubes
DOI: 10.12677/AAM.2016.54084, PDF,  被引量    国家自然科学基金支持
作者: 白灿, 王贞化：数学与信息科学学院，河南师范大学，河南 新乡；王世英*：数学与信息科学学院，河南师范大学，河南 新乡；河南省大数据统计分析与优化控制工程实验室，河南师范大学，河南 新乡
关键词: 互连网络；Mo¨bius立方体；1好邻诊断度；Interconnection Network； Mo¨bius Cube； 1-Good-Neighbor Diagnosability
摘要: 在计算机领域，多处理器系统的诊断度是一项重要的研究课题。在传统的诊断度中，任一处理器的所有相邻处理器可以同时出现故障。但是，在处理器系统中，出现这种情况的概率极小。因此，peng等在2012年提出了g好邻诊断度，它限制每个非故障顶点至少有g个非故障邻点。作为超立方体的变形，n维Mo¨bius立方体有着比超立方体更好的性质。本文证明了MQn的1好邻连通度是2n-2，又证明了MQn在PMC模型下(n≥4)和在MM*模型下(n≥5)的1好邻诊断度是2n-2。
Abstract: In the field of computers, the diagnosability of a multiprocessor is an important study topic. The traditional diagnosability allows that all neighbors of some vertices are faulty at the same time. However, in the processor system, the probability of this kind of situation is very small. Therefore, in 2012, Peng et al. proposed the g-good-neighbor diagnosability. It restrains every fault-free node containing at least g fault-free neighbors. As hypercube variants, the n-dimensional Mo¨bius cube MQn has some better properties than hypercubes. This paper shows that the 1-good-neighbor connectivity of MQn is 2n-2 (n≥4), and the 1-good-neighbor diagnosability of MQn is  under the PMC model (n≥4) and under the MM* model (n≥5).

 

文章引用：白灿, 王世英, 王贞化. Mo¨bius立方体的1好邻连通度和诊断度[J]. 应用数学进展, 2016, 5(4): 728-737. https://dx.doi.org/10.12677/AAM.2016.54084

参考文献

[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, 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. [Google Scholar] [CrossRef] 
[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 Computation, 218, 10406-10412. [Google Scholar] [CrossRef] 
[5] Wang, S.Y. and Han, W.P. (2016) The g-Good-Neighbor Conditional Diagnosability of n-Dimensional Hypercubes under the MM* Model. Information Processing Letters, 116, 574-577. [Google Scholar] [CrossRef] 
[6] 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 Parallel and Distributed Systems, 26, 1165-1177. [Google Scholar] [CrossRef] 
[7] Yuan, J., Liu, A.X., Qin, X., Zhang, J.F. and Li, J. (2016) g-Good-Neighbor Conditional Diagnosability Measure of 3-Ary n-Cube Networks. Theoretical Computer Science, 626, 144-162
[8] Ma, X.L., Wang, S.Y. and Wang, Z.H. (2016) The 1-Good-Neighbor Connectivity and Diagnosability of Crossed Cube. Advance in Applied Mathematics, 5, 282-290.
[9] Wang, M., Guo, Y.B. and Wang, S.Y. (2015) The 1-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. International Journal of Computer Mathematics, 1-12. [Google Scholar] [CrossRef] 
[10] Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.
[11] Cull, P. and Larson, S.M. (1995) The Möbius Cubes. IEEE Transactions on Computers, 44, 647-659. [Google Scholar] [CrossRef] 
[12] Fan, J.X. (1998) Diagnosability of Möbius Cubes. IEEE Transactions on Parallel and Distributed Systems, 9, 923-928. [Google Scholar] [CrossRef] 

为你推荐