|
|
扩展k元n立方体的1-好邻诊断度
|
Abstract:
现如今，一个多重处理器系统的诊断度是一个非常重要的研究课题，它是度量多重处理器系统故障诊断能力的重要参数。2012年，Peng等人提出了一个新的系统故障诊断方法，称为g好邻诊断度，它限制每个非故障顶点至少有g个非故障邻点。n维扩展k元n立方体是超立方体的一个重要变形。在本文中，我们证明了扩展k元n立方体在PMC模型下和MM*模型下的1-好邻诊断度是8n-9(n≥4,k≥4)。
Nowadays, diagnosability is an important research topic and parameter in measuring the fault di-agnosis of multiprocessor systems. In 2012, Peng et al. proposed a new measure for fault diagnosis of the system, which was called g-good-neighbor diagnosability that restrained every fault-free node containing at least g fault-free neighbors. The n-dimensional augmented k-ary n-cube is an important variant of the hypercube. In this paper, we prove that the 1-good-neighbor diagnosibility of augmented k-aryn-cube under the PMC model and the MM* model is 8n-9 forn≥4,k≥4.
| [1] | 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 |
| [2] | 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 |
| [3] | 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. |
| [4] | Joon, M. and Miroslaw, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multipro-cessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, Portland, June 1981, 173-175. |
| [5] | Chang, N.W., Cheng, E. and Hsieh, S. (2015) Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model. ACM Transactions on Design Automation of Electronic Systems, 20, 1-16.
https://doi.org/10.1145/2699854 |
| [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. https://doi.org/10.1109/TPDS.2014.2318305 |
| [7] | 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 |
| [8] | 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 Com-puter Science, 622, 144-162. |
| [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] | Wang, M., Guo, Y.B. and Wang, S.Y. (2015) The 1-Good-Neighbor Di-agnosability 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 |
| [11] | 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 |
| [12] | Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York. |
| [13] | 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 |
