The pessimistic diagnosability of graphs and its applications to four kinds of interconnection networks

References

• S.B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput. 38(4) (1989), pp. 555–566.
   Web of Science ®Google Scholar
• A. Bondy and U.S.R. Murty, Graph Theory, Springer, New York, 2007.
   Google Scholar
• S.-Y. Chen and S.-S. Kao, Hamiltonian connectivity and globally 3*-connectivity of dual-cube extensive networks, Comput. Electr. Eng. 36 (2010), pp. 404–413.
   Web of Science ®Google Scholar
• C. Chin, T.-H. Weng, L.-H. Hsu, and S.-C. Chiou, The spanning connectivity of the burnt pancake graphs, IEICE Trans. Inform. Syst. E92-D(3) (2009), pp. 389–400.
   Google Scholar
• K.Y. Chwa and S.L. Hakimi, On fault identification in diagnosable systems, IEEE Trans. Comput. 30(6) (1981), pp. 414–422.
   Web of Science ®Google Scholar
• J. Fan, Diagnosability of the Möbius cubes, IEEE Trans. Parallel Distrib. Syst. 40(1) (1991), pp. 88–93.
   Google Scholar
• J. Fan and L. He, BC interconnection networks and their properties, Chinese J. Comput.-Chin. Ed. 26(1) (2003), pp. 84–90.
   Google Scholar
• J. Fan and X. Lin, The t/k-diagnosability of the BC graphs, IEEE Trans. Comput. 54(2) (2005), pp. 176–184.
   Web of Science ®Google Scholar
• M.-M. Gu and R.-X. Hao, The pessimistic diagnosability of three kinds of graphs, Discrete Appl. Math. 217 (2017), pp. 548–556.
   Web of Science ®Google Scholar
• M.-M. Gu, R.-X. Hao, and Y.-Q. Feng, The pessimistic diagnosability of bubble-sort star graphs and augmented k-ary n-cubes, Int. J. Comput. Math. 1 (2016), pp. 98–112.
   Google Scholar
• R.-X. Hao, M.-M. Gu, and Y.-Q. Feng, The pessimistic diagnosabilities of some general regular graphs, Theor. Comput. Sci. 609 (2016), pp. 413–420.
   Web of Science ®Google Scholar
• T. Iwasaki and K. Kaneko, Fault-tolerant routing in burnt pancake graphs, Inform. Process. Lett. 110 (2010), pp. 535–538.
   Web of Science ®Google Scholar
• A. Kanevsky and C. Feng, On the embedding of cycles in pancake graphs, Parallel Comput. 21 (1995), pp. 923–936.
   Web of Science ®Google Scholar
• A. Kavianpour and A.D. Friedman, Efficient design of easily diagnosable systems, Proc. 3rd USA-Japan Comput. Conf., 1978, pp. 251–257
   Google Scholar
• Y. Li and S. Peng, Dual-cubes: A new interconnection networks for high-performance computer cluster, Proceedings of the 2000 International Computer Symposium, Workshop on Computer Architecture, 2000, pp. 51–57
   Google Scholar
• Y. Li, S. Peng, and W. Chu, Hamiltonian cycle embedding for fault tolerance in dual-cube, IASTED International Conference on Networks, Parallel. Distr. Process. Appl., 2002, pp. 1–6
   Google Scholar
• Y. Li, S. Peng, and W. Chu, Fault-tolerant cycle embedding in dual-cube with node faults, Int. J. High Perform. Comput. Netw. 3(1) (2005), pp. 45–53.
   Google Scholar
• C.-K. Lin, H.-M. Huang, and L.-H. Hsu, The super connectivity of the pancake graphs and the super laceability of the star graphs, Theor. Comput. Sci. 339 (2005), pp. 257–271.
   Web of Science ®Google Scholar
• J. Maeng and M. Malek, A comparison connection assignment for self-diagnosis of multiprocessors systems, Proc. 11th Int. Symp. Fault-Tolerant Computing, 1981, pp. 173–175
   Google Scholar
• F.P. Preparata, G. Metze, and R.T. Chien, On the connection assignment problem of diagnosis systems, IEEE Trans. Electron. Comput. 16(12) (1967), pp. 848–854.
   Web of Science ®Google Scholar
• A. Sengupta and A.T. Dahbura, On self-diagnosable multiprocesor systems, diagnosis by the comparison approach, IEEE Trans. Comput. 41(11) (1992), pp. 1386–1396.
   Web of Science ®Google Scholar
• S. Song, X. Li, S. Zhou, and M. Chen, Fault tolerance and diagnosability of burnt pancake networks under the comparision model, Theor. Comput. Sci. 582 (2015), pp. 48–59.
   Web of Science ®Google Scholar
• Y. Suzuki and K. Kaneko, An algorithm for node-disjoint paths in pancake graphs, IEICE Trans. Inform. Syst. 3 (2003), pp. 610–615.
   Google Scholar
• C.-H. Tsai, The pessimistic diagnosability of alternating group graphs under the PMC model, Inform. Process. Let. 115 (2015), pp. 151–154.
   Web of Science ®Google Scholar
• C.-H. Tsai and J.-C. Chen, Fault isolation and identification in general biswapped networks under the PMC diagnostic model, Theor. Comput. Sci. 501 (2013), pp. 62–71.
   Web of Science ®Google Scholar
• A.S. Vaidya, P.S.N. Rao, and S.R. Shankar, A class of hypercube-like networks, Proc. 5th IEEE Symp. Parallel Distrib. Process., 1993, pp. 800–803
   Google Scholar
• C.L. Yang, G.M. Marson, and R. Leonetti, On fault identification and isolation in t1/t1-diagnosable systems, IEEE Trans. Comput. C-35(7) (1986), pp. 639–644.
   Web of Science ®Google Scholar
• X. Yang and S. Zhou, On conditional fault tolerant of dual-cubes, Int. J. Parallel. Emergent. Distrib. Syst. 28(3) (2013), pp. 199–213.
   Google Scholar
• L.-C. Ye, J.-R. Liang, and H.-X. Lin, A fast pessimistic diagnosis algorithm for hypercube-like networks under the comparison model, IEEE Trans. Comput. 65(9) (2016), pp. 2884–2888.
   Web of Science ®Google Scholar