Research ArticleOpen AccessGoogle Scholar indexed
The 2-Extra Diagnosability of Alternating Group Graphs under the PMC Model and MM* Model
School of Mathematics and Information Science, Henan Normal University, Xinxiang, China
School of Mathematics and Information Science, Henan Normal University, Xinxiang, China
- 1 School of Mathematics and Information Science, Henan Normal University, Xinxiang, China
- 2 School of Mathematics and Information Science, Henan Normal University, Xinxiang, China
American Journal of Computational Mathematics·Volume 08 (2018)·Pages 42–54·Published 23 February 2018·DOI10.4236/ajcm.2018.81004
Copy link · social · email
Abstract
Diagnosability of a multiprocessor system is one important study topic. In 2015, Zhang <i> et al. </i> proposed a new measure for fault diagnosis of the system, namely, <i> g</i> -extra diagnosability, which restrains that every fault-free component has at least (<i>g</i> + 1) fault-free nodes. As a favorable topology structure of interconnection networks, the <i>n</i> -dimensional alternating group graph <i> AG n</i> has many good properties. In this paper, we give that the 2-extra diagnosability of <i> AG n</i> is 6<i>n</i> - 17 for <i>n</i> ≥ 5 under the PMC model and MM * model.
KeywordsInterconnection NetworkDiagnosabilityAlternating Group Graph
- 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
- Fan, J. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104. https://doi.org/10.1109/TPDS.2002.1041887
- 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
- Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Computers, EC-16, 848-854. https://doi.org/10.1109/PGEC.1967.264748
- Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, 173-175.
- Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under PMC Model. Applied Mathematics and Computation, 218, 10406-10412. https://doi.org/10.1016/j.amc.2012.03.092
- Wang, S. and Han, W. (2016) The g-Good-Neighbor Conditional Diagnosability of n-Dimensional Hypercubes under the MM* Model. Information Processing Letters, 116, 574-577. https://doi.org/10.1016/j.ipl.2016.04.005
- Yuan, J., Liu, A., Ma, X., Liu, X., Qin, X. and Zhang, J. (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
- Yuan, J., Liu, A., Qin, X., Zhang, J. and Li, J. (2016) g-Good-neighbor Conditional Diagnosability Measures for 3-Ary n-Cube Networks. Theoretical Computer Science, 622, 144-162. http://doi.org/10.1016/j.tcs.2016.01.046
- Wang, M., Guo, Y. and Wang, S. (2017) The 1-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. International Journal of Computer Mathematics, 94, 620-631. http://doi.org/10.1080/00207160.2015.1119817
- Wang, M., Lin, Y. and Wang, S. (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. http://doi.org/10.1016/j.tcs.2016.03.019