Journal of the Operations Research Society of China >

2023 , Vol. 11 >Issue 4: 891 - 910

DOI: https://doi.org/10.1007/s40305-022-00415-7

The Non-Inclusive Diagnosability of Regular Graphs

Expand
  • 1. School of Mathematical Sciences, Beijing Normal University, Laboratory of Mathematics and Complex Systems, Ministry of Education, Beijing, 100875, China;
    2. Department of Mathematics, Taiyuan University of Technology, Taiyuan, 030024, China

Received date: 2021-10-08

  Revised date: 2022-02-28

  Online published: 2023-12-26

Supported by

This research is supported by the National Natural Science Foundation of China (No. 11571044) and the Natural Science Foundation of Shanxi Province (No. 201901D211106).

Fold

Abstract

Fault diagnosis is an important area of study with regard to the design and maintenance of multiprocessor systems. A new measure for fault diagnosis of systems, namely, non-inclusive diagnosability (denoted by tN(G)), was proposed by Ding et al. In this paper, we establish the non-inclusive diagnosability of a class of regular graphs under the PMC model and the MM* model. As applications, the non-inclusive diagnosabilities of hypercubes, hierarchical hypercubes, folded hypercubes, star graphs, bubble-sort graphs, pancake graphs and dual cubes are determined under the PMC model and the MM* model.

Key words： PMC model; MM* model; Regular graph; Fault diagnosability

Cite this article

Yu-Long Wei, Tong-Tong Ding, Min Xu . The Non-Inclusive Diagnosability of Regular Graphs[J]. Journal of the Operations Research Society of China, 2023 , 11(4) : 891 -910 . DOI: 10.1007/s40305-022-00415-7

References

[1] Preparata, F.P., Metze, G., Chien, R.T.: On the connection assignment problem of diagnosable systems. IEEE Trans. Electron. Comput. EC-16(6), 848-854 (1967)
[2] Maeng, J., Malek, M.: A comparison connection assignment for self-diagnosis of multiprocessor systems. In: Proceedings of 11th International Symposium on Fault-Tolerant Computing, pp. 173-175 (1981)
[3] Sengupta, A., Dahbura, A.T.: On self-diagnosable multiprocessor system: diagnosis by the comparison approach. IEEE Trans. Comput. 41(11), 1386-1396 (1992)
[4] Chang, G.Y., Chang, G.J., Chen, G.H.: Diagnosabilities of regular networks. IEEE Trans. Parallel Distrib. Syst. 16(4), 314-323 (2005)
[5] Chang, N.W., Hsieh, S.Y.: Structural properties and conditional diagnosability of star graphs by using PMC model. IEEE Trans. Parallel Distrib. Syst. 25(11), 3002-3011 (2014)
[6] Cheng, E., Qiu, K., Shen, Z.: A general approach to deriving the g-good-neighbor conditional diagnosability of interconnection networks. Theor. Comput. Sci. 757, 56-67 (2019)
[7] Fan, J.X., Lin, X.L.: The t/k-diagnosability of the BC graphs. IEEE Trans. Comput. 54, 176-184 (2005)
[8] Ding, T.T., Xu, M., Zhu, Q.: The non-inclusive diagnosability of hypercubes under the MM* model. Int. J. Found. Comput. Sci. 31(7), 929-940 (2020)
[9] Hao, R.X., Tian, Z.X., Xu, J.M.: Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs. Theor. Comput. Sci. 627, 36-53 (2016)
[10] Hsu, G.H., Tan, J.J.M.: A local diagnosability measure for multiprocessor systems. IEEE Trans. Parall. Distrib. Syst. 18, 598-607 (2007)
[11] 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)
[12] Lee, C.W., Hsieh, S.Y.: Diagnosability of two-matching composition networks under the MM* model. IEEE Trans. Depend. Secure Comput. 8(2), 246-255 (2011)
[13] Li, X.Y.: Strong diagnosability and conditional diagnosability of optical multi-mesh hypercube networks under the PMC model. Int. J. Comput. Math. 93(12), 2054-2063 (2016)
[14] Lin, L.M., Hsieh, S.Y., Xu, L., Zhou, S.M., Chen, R.Q.: The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model. J. Comput. System Sci. 95, 1-18 (2018)
[15] Peng, S.L., Lin, C.K., Tan, J.J.M., Hsu, L.H.: The g-good-neighbor conditional diagnosability of hypercube under the PMC model. Appl. Math. Comput. 218, 10406-10412 (2012)
[16] Wang, S.Y., Yang, Y.X.: The 2-good-neighbor (2-extra) diagnosability of alternating group graph networks under the PMC model and MM* model. Appl. Math. Comput. 305, 241-250 (2017)
[17] Wei, Y.L., Xu, M.: Conditional diagnosability of Cayley graphs generated by wheel graphs under the PMC model. Theor. Comput. Sci. 849, 163-172 (2021)
[18] Wei, Y.L., Xu, M.: Hybrid fault diagnosis capability analysis of regular graphs. Theor. Comput. Sci. 760, 1-14 (2019)
[19] Wei, Y.L., Xu, M.: On g-good-neighbor conditional diagnosability of (n, k) -star networks. Theor. Comput. Sci. 697, 79-90 (2017)
[20] Wei, Y.L., Xu, M.: The g-good-neighbor conditional diagnosability of locally twisted cubes. J. Oper. Res. Soc. China 6(2), 333-347 (2018)
[21] Wei, Y.L., Xu, M.: The 1, 2 -good-neighbor conditional diagnosabilities of regular graphs. Appl. Math. Comput. 334, 295-310 (2018)
[22] Xu, M., Thulasiraman, K., Hu, X.D.: Conditional diagnosability of matching composition networks under the PMC model. IEEE Trans. Circuits Syst. II: Express Briefs 56(11), 875-879 (2009)
[23] Xu, M., Thulasiraman, K., Zhu, Q.: Conditional diagnosability of a class of matching composition networks under the comparison model. Theor. Comput. Sci. 674, 43-52 (2017)
[24] Xu, M., Wei, Y.L.: The h-edge tolerable diagnosability of balanced hypercubes. Theor. Comput. Sci. 795, 540-546 (2019)
[25] Yuan, J., Liu, A.X., Ma, X., Qin, X., Zhang, J.: The g-good-neighbor conditional diagnosability of k-ary n -cubes under the PMC model and MM* model. IEEE Trans. Parallel Distrib. Syst. 26(4), 1165-1177 (2015)
[26] Zhang, S., Yang, W.: The g-extra conditional diagnosability and sequential t/k-diagnosability of hypercubes. Int. J. Comput. Math. 93(3), 482-497 (2016)
[27] Zhou, S.M., Chen, L.X., Xu, J.M.: Conditional fault diagnosability of dual-cubes. Internat. J. Found. Comput. Sci. 23(8), 1729-1749 (2012)
[28] Zhou, S.M., Lin, L.M., Xu, J.M.: Conditional fault diagnosis of hierarchical hypercubes. Int. J. Comput. Math. 89(16), 2152-2164 (2012)
[29] Zhu, Q., Guo, G.D., Tang, W.L., Zhang, C.Q.: A diagnosis algorithm by using graph-coloring under the PMC model. J. Comb. Optim. 32, 960-969 (2016)
[30] Zhu, Q., Li, L.L., Liu, S.Y., Zhang, X.: Hybrid fault diagnosis capability analysis of hypercubes under the PMC model and MM* model. Theor. Comput. Sci. 758, 1-8 (2019)
[31] Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. The Macmillan Press Ltd, New York (1976)
[32] Dahbura, A.T., Masson, G.M.: An O(n2.5) faulty identification algorithm for diagnosable systems. IEEE Trans. Comput. 33(6), 486-492 (1984)
[33] Saad, Y., Schultz, M.H.: Topological properties of hypercubes. IEEE Trans. Comput. 37(7), 867-872 (1988)
[34] Malluhi, Q.M., Bayoumi, M.A.: The hierarchical hypercube: a new interconnection topology for massively parallel systems. IEEE Trans. Parallel Distrib. Syst. 5(1), 17-30 (1994)
[35] El-Amawy, A., Latifi, S.: Properties and performance of folded hypercubes. IEEE Trans. Parallel Distrib. Syst. 2(1), 31-42 (1991)
[36] Xu, J.M., Ma, M.J.: Cycles in folded hypercubes. Appl. Math. Lett. 19, 140-145 (2006)
[37] Zhu, Q., Xu, J.M., Hou, X.M., Xu, M.: On reliability of the folded hypercubes. Inform. Sci. 177, 1782-1788 (2007)
[38] Akers, S.B., Krishnamurthy, B.: A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput. 38(4), 555-566 (1989)
[39] Kanevsky, A., Feng, C.: On the embedding of cycles in pancake graphs. Parallel Comput. 21, 923-936 (1995)
[40] Li, Y., Peng, S.: Dual-cubes: a new interconnection network for high-performance computer clusters. In: Proceedings of the 2000 International Computer Symposium, Workshop on Computer Architecture. pp 51-57 (2000)
Options
Outlines

/

〈 〉

Copyright © Operations Research Society of China, The Periodicals Agency of Shanghai University , and Springer-Verlag Berlin Heidelberg 2016