Conditional diagnosability of bubble-sort star graphs. (English) Zbl 1329.05271
Summary: Diagnosability plays an important role in measuring the reliability of interconnection networks. Conditional faulty set is a special faulty set that does not contain all of neighbors of any vertex in a network. The conditional diagnosability is a metric that can give the maximum cardinality of the conditional faulty sets that the system is guaranteed to identify. This paper shows that the conditional diagnosability of the bubble-sort star graph BSnBSn under the MM model is \(6n-15\) for \(n\geq 6\) and under the PMC model is \(8n-21\) for \(n\geq 5\).
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
Keywords:
interconnection networks; conditional diagnosability; MM model; PMC model; bubble-sort star graphsReferences:
| [1] | Cai, H.; Liu, H.; Lu, M., Fault-tolerant maximal local-connectivity on Bubble-sort star graphs, Discrete Appl. Math., 181, 33-40 (2015) · Zbl 1304.05085 |
| [2] | Chang, N. W.; Hsieh, S. Y., Conditional diagnosability of augmented cubes under the PMC model, IEEE Trans. Dependable Secure Comput., 9, 1, 46-60 (2012) |
| [3] | Chang, N. W.; Hsieh, S. Y., Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Trans. Parallel Distrib. Syst., 25, 11, 3002-3011 (2014) |
| [4] | Chang, N. W.; Lin, T. Y.; Hsieh, S. Y., Conditional diagnosability of \(k\)-Ary \(n\)-Cubes under the PMC model, ACM Trans. Des. Autom. Electron. Syst., 17, 46 (2012) |
| [5] | Chen, E.; Qiu, K. Y.; Shen, Z., On the conditional diagnosability of matching composition networks, Theoret. Comput. Sci., 557, 101-114 (2014) · Zbl 1338.68028 |
| [7] | Fan, J., Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Trans. Parallel Distrib. Syst., 13, 7, 687-692 (2002) |
| [8] | Fan, J.; Lin, X., The \(t / k\)-diagnosability of the BC graphs, IEEE Trans. Comput., 54, 2, 176-184 (2005) |
| [9] | Fan, J.; Yang, J.; Zhao, G.; Zhang, W., Diagnosable evaluation of DCC linear congruential graphs under the PMC diagnostic model, Inform. Sci., 179, 11, 1785-1791 (2009) · Zbl 1176.68034 |
| [10] | Hsieh, S. Y.; Chuang, T. Y., The strong diagnosability of regular networks and product networks under the PMC model, IEEE Trans. Parallel Distrib. Syst., 20, 3, 367-378 (2009) |
| [11] | Hsieh, S. Y.; Kao, C. Y., The conditional diagnosability of \(k\)-Ary \(n\)-Cubes under the comparison diagnosis model, IEEE Trans. Comput., 62, 4, 839-843 (2013) · Zbl 1365.68085 |
| [12] | Hsieh, S. Y.; Tsai, C. Y.; Chen, C. A., Strong diagnosability and conditional diagnosability of multiprocessor systems and folded hypercubes, IEEE Trans. Comput., 62, 7, 1472-1477 (2013) · Zbl 1365.94699 |
| [13] | Hsu, G. H.; Chiang, C. F.; Shih, L. M.; Hsu, L. H.; Tan, J. J.M., Conditional diagnosability of hypercubes under the comparison diagnosis model, J. Sys. Archit., 55, 2, 140-146 (2009) |
| [14] | Lai, P. L.; Tan, J. J.M.; Chang, C. P.; Hsu, L. H., Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput., 54, 2, 165-175 (2005) |
| [15] | Lin, C. K.; Tan, J. J.M.; Hsu, L. H.; Cheng, E.; Lipták, L., Conditional diagnosability of cayley graphs generated by transposition trees under the comparison diagnosis model, J. Interconnect. Netw., 9, 1/2, 83-97 (2008) |
| [16] | Lin, C. K.; Teng, Y. H., The diagnosability of triangle-free graphs, Theoret. Comput. Sci., 530, 58-65 (2014) · Zbl 1359.68030 |
| [18] | Preparata, F. P.; Metze, G.; Chien, R. T., On the connection assignment problem of diagnosable systems, IEEE Trans. Comput., 16, 6, 448-454 (1967) · Zbl 0189.16904 |
| [19] | Sengupta, A.; Dahbura, A. T., On self-diagnosable multiprocessor systems: Diagnosis by the comparison approach, IEEE Trans. Comput., 41, 11, 1386-1396 (1992) · Zbl 1395.68062 |
| [20] | Wang, D., Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model, IEEE Trans. Comput., 48, 12, 1369-1374 (1999) · Zbl 1392.68061 |
| [21] | Zheng, J.; Latifi, S.; Regentova, E.; Luo, K.; Wu, Xiaolong, Diagnosability of star graphs under the comparison diagnosis model, Inform. Process. Lett., 93, 1, 29-36 (2005) · Zbl 1173.68615 |
| [22] | Zhou, S.; Wang, J.; Xu; Xu, J. M., Conditional fault diagnosis of bubble sort graphs under the PMC model, Intell. Comput. Evol. Comput., 53-59 (2013) |
| [23] | Zhu, Q., On conditional diagnosability and reliability of the BC networks, J. Supercomput., 45, 4, 173-184 (2008) |
| [24] | Zhu, Q.; Liu, S. Y.; Xu, M., On conditional diagnosability of the folded hypercubes, Inform. Sci., 178, 4, 1069-1077 (2008) · Zbl 1134.68014 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
