有缺失边的n维增强超立方体在MM*模型下的局部可诊断性
Local Diagnosability of n-Dimensional Enhanced Hypercubes with Missing Edges under the MM* Model
摘要: 多重处理器系统的诊断性在互联网的可靠性中扮演着重要的角色。n维增强超立方体Qn,k是由n维超立方体Qn添加一些互补边得到的。n维增强超立方体Qn,k有许多好的性质。这篇文章中，我们首先证明了在MM*模型下Qn,k具有强局部诊断性，然后证明了在MM*模型下Qn,k即使存在n-1条缺失边时仍具有强局部诊断性，并且证明了缺失边的数目n-1是最优值。
Abstract: The diagnosability of multiprocessor systems plays an important role in the reliability of the Internet. The n-dimensional enhanced hypercube Qn,k is obtained by adding some complementary edges to n-dimensional hypercubes. The n-dimensional enhanced hypercube Qn,k has many good properties. In this paper, we prove Qn,k has the strong local diagnosability property under the MM* model. Then we prove that Qn,k(n≤6) keeps the strong local diagnosability property even if there exist n-1 missing edges in it under the MM* model and the result is optimal with respect to the number of missing edges.
文章引用：王世英, 张雪芳, 赵丽娜. 有缺失边的n维增强超立方体在MM*模型下的局部可诊断性[J]. 应用数学进展, 2022, 11(2): 726-738. https://doi.org/10.12677/AAM.2022.112079

参考文献

[1] Feng, W. and Wang, S. (2020) The Diagnosability of Wheel Networks with Missing Edges under the Comparison Model. Mathematics, 8, Article No. 1818. [Google Scholar] [CrossRef] 
[2] Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessors Systems. Proceeding of the 11th International Symposium on Fault-Tolerant Computing, Portland, 24-26 June 1981, 173-175.
[3] Sengupta, A. and Dahbura, A.T. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396. [Google Scholar] [CrossRef] 
[4] Dahbura, A.T. and Masson, G.M. (1984) An Fault identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492. [Google Scholar] [CrossRef] 
[5] 樊畅畅, 王世英, 马晓蕾. 有遗失边的n维超立方体和折叠超立方体在MM*模型下的诊断度[J]. 应用数学进展, 2021, 10(1): 150-159. [Google Scholar] [CrossRef] 
[6] Hsu, G.-H. and Tan, J.J.M. (2007) A Local Diagnosability Measure for Multiprocessor Systems. IEEE Transactions on Parallel and Distributed Systems, 18, 598-607. [Google Scholar] [CrossRef] 
[7] Chiang, C.-F. and Tan, J.J.M. (2009) Using Node Diagnosability to Determine t-Diagnosability under the Comparison Diagnosis Model. IEEE Transactions on Computers, 58, 251-259. [Google Scholar] [CrossRef] 
[8] Chiang, C.-F., Hsu, G.-H., Shih, L.-M. and Tan, J.J.M. (2012) Diagnosability of Star Graphs with Missing Edges. Information Sciences, 188, 253-259. [Google Scholar] [CrossRef] 
[9] Cheng, E. and Lipták, L. (2013) Diagnosability of Cayley Graphs Generated by Transposition Trees with Missing Edges. Information Sciences, 238, 250-252. [Google Scholar] [CrossRef] 
[10] Cheng, E., Lipták, L. and Steffy, D.E. (2013) Strong Local Diagnosability of -Star Graphs and Cayley Graphs Generated by 2-Trees with Missing Edges. Information Processing Letters, 113, 452-456. [Google Scholar] [CrossRef] 
[11] Hsieh, S. (2006) Fault-Tolerant Cycles Embedding in the Hypercube with More Both Faulty Vertices and Faulty Edges. Parallel Computing, 32, 84-91. [Google Scholar] [CrossRef] 
[12] Li, T.-K., Tsai, C.H., Tan, J.J.M. and Hsu, L.-H. (2003) Bipanconnectivity and Edge-Fault-Tolerant Bipancyclicity of Hypercubes. Information Processing Letters, 87, 107-110. [Google Scholar] [CrossRef] 
[13] Tsai, C.-H., Tan, J.J.M., Liang, T. and Hsu, L.-H. (2002) Fault-Tolerant Hamiltonian Laceability of Hypercubes. Information Processing Letters, 83, 301-306. [Google Scholar] [CrossRef] 
[14] Tsai, C.-H. (2007) Cycles Embedding in Hypercubes with Node Failures. Information Processing Letters, 102, 242-246. [Google Scholar] [CrossRef] 
[15] Tzeng, N.F. and Wei, S. (1991) Enhanced Hypercube. IEEE Transactions on Computers, 40, 284-294. [Google Scholar] [CrossRef] 
[16] Liu, H. (2009) The Structural Features of Enhanced Hypercube Networks. Proceedings of the 5th International Conference on Natural Computation, Tianjian, 14-16 August 2009, 345-348. [Google Scholar] [CrossRef] 
[17] Liu, H. (2008) Properties and Performance of Enhanced Hypercube Networks. Fourth International Conference on Networked Computing and Advanced Information Management, Vol. 1, Gyeongju, 2-4 September 2008, 580-583. [Google Scholar] [CrossRef] 
[18] Wang, D. (1999) Diagnosability of Hypercubes and Enhanced Hypercubes under the Comparison Diagnosis Model. IEEE Transactions on Computers, 48, 1369-1374. [Google Scholar] [CrossRef] 
[19] Sabir, E., Mamut, A. and Vumar, E. (2019) The Extra Connectivity of the Enhanced Hypercubes. Theoretical Computer Science, 799, 22-31. [Google Scholar] [CrossRef] 
[20] Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, New York.
[21] Liu, M. and Liu, H. (2013) Paths and Cycles Embedding on Faulty Enhanced Hypercube Networks. Acta Mathematica Scientia, 33, 227-246. [Google Scholar] [CrossRef] 
[22] Yuan, J., Liu, A., Ma, X., Liu, X. and Qin, X. (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] 

为你推荐