A general approach to deriving diagnosability results of interconnection networks*

References

• Cheng E, Mao YP, Qiu K, et al. Faulty nodemodeling and diagnosis in interconnection networks (Extended abstract). In: Proceedings 2019 International Conference on Modeling, Simulation, Optimization and Algorithm (ICMSOA 2019), November 9-10, 2019. Sanya: IOP Publishing; 2019. p. 012024. (J. Phys: Conf. Ser.; vol. 1409).
   Google Scholar
• Harary F, Hayes JP, Wu H-J. A survey of the theory of hypercube graphs. Comp Math Appl. 1988;15(4):277–289.
   Web of Science ®Google Scholar
• Akers SB, Krishnamurthy B. A group theoretic model for symmetric interconnection networks. IEEE Trans Comput. 1989;38(4):555–566.
   Web of Science ®Google Scholar
• Chou ZT, Hsu CC, Sheu JP. Bubblesort star graphs: a new interconnection network. In: Proceedings of 1996 International Conference on Parallel and Distributed Systems; June 3-6; Tokyo, Japan: IEEE Computer Society Press; 1996. p. 41–48.
   Google Scholar
• Day K, Tripathi A. Arrangement graphs: a class of generalized star graphs. Inform Process Lett. 1992;42:235–241.
   Web of Science ®Google Scholar
• Chiang WK, Chen RJ. The (n,k)-star graph: a generalized star graph. Inform Proc Lett. 1995;56:259–264.
   Web of Science ®Google Scholar
• Hakimi SL, Amin AT. Characterization of connection assignment of diagnosable systems. IEEE Trans Comput. 1974;23(1):86–88.
   Web of Science ®Google Scholar
• Lin CK, Tan JJM, Hsu LH, et al. Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model. J Interconnect Netw. 2008;9(1):83–97.
   Google Scholar
• Preparata FP, Metze G, Chien RT. On the connection assignment problem of diagnosable systems. IEEE Trans Electron Comput. 1967;EC-16(6):848–854.
   Google Scholar
• Cheng E, Liptak L, Qiu K, et al. On the conditional diagnosability of the interconnection networks. Inform Process Lett. 2012;112:674–677.
   Web of Science ®Google Scholar
• Hong WS, Hsieh SY. Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model. IEEE Trans Reliab. 2012;61:140–148.
   Web of Science ®Google Scholar
• Lai PL, Tan JJM, Chang CP, et al. Conditional diagnosability measures for large multiprocessor systems. IEEE Trans Comput. 2005;54:165–175.
   Web of Science ®Google Scholar
• Peng SL, Lin CK, Tan JJM, et al. The g-good-neighbor conditional diagnosability of hypercube under the PMC model. Appl Math Comput. 2012;218(21):10406–10412.
   Web of Science ®Google Scholar
• Fàbrega J, Fiol MA. On the extraconnectivity of graphs. Discrete Math. 1996;155:49–57.
   Web of Science ®Google Scholar
• Zhang S, Yang W. The g-extra conditional diagnosability and sequential t/k-diagnosability of hypercubes. Int J Comput Math. 2016;93(3):482–497.
   Web of Science ®Google Scholar
• Cheng E, Hao R, Shen Z. Structural properties and fault resiliency of interconnection networks. In: Adamatzky A, Akl S, Sirakoulis G, editors. From parallel to emergent computing. Boca Raton (FL): CRC Press; 2019. p. 77–101.
   Google Scholar
• Sengupta A, Dahbura AT. On self-diagnosable multiprocessor systems: diagnosis by the comparison approach. IEEE Trans Comput. 1992;41:1386–1396.
   Web of Science ®Google Scholar
• Maeng J, Malek M. A comparison connection assignment for self-diagnosis of multiprocessor systems. In: Proceeding of 11th International Symposium on Fault-Tolerant Computing. 1981. p. 173–175.
   Google Scholar
• Malek M. A comparison connection assignment for diagnosis of multiprocessor systems. In: Proceeding of 7th International Symposium on Computer Architecture. 1980. p. 31–35.
   Google Scholar
• Dahbura AT, Masson GM. An n2.5 faulty identification algorithm for diagnosable systems. IEEE Trans Comput. 1984;33(6):486–492.
   Web of Science ®Google Scholar
• Sullivan GF. A polynomial time algorithm for fault diagnosability. In: Proceeding of 25th Annual Symposium on Foundations Computer Science. IEEE Computer Society; 1984. p. 148–156.
   Google Scholar
• Zhu Q. On conditional diagnosability and reliability of the BC networks. J Supercomput. 2008;45:173–184.
   Web of Science ®Google Scholar
• Barsi F, Grandoni F, Maestrini P, et al. A theory of diagnosability of digital systems. IEEE Trans Comput. 1976;25(6):585–593.
   Web of Science ®Google Scholar
• Xu L, Lin L, Zhou S, et al. The extra connectivity, extra conditional diagnosability, and t/m -diagnosability of arrangement graphs. IEEE Trans Reliab. 2016;65(3):1–15.
   Web of Science ®Google Scholar
• Wang S, Wang Z, Wang M. The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks. Comput J. 2016;59(12):1839–1856.
   Web of Science ®Google Scholar
• Lv MJ, Zhou SM, Sun XL, et al. Reliability of (n,k)-star network based on g -extra conditional fault. Theor Comput Sci. 2019;757:44–55.
   Web of Science ®Google Scholar
• Liu HQ, Zhang SZ, Li D. On g-extra conditional diagnosability of hierarchical cubic networks. Theor Comput Sci. 2019;790:66–79. doi:https://doi.org/10.1016/j.tcs.2019.04.028.
   Web of Science ®Google Scholar
• Cheng E, Qiu K, Shen Z. A general approach to deriving the g-good-neighbor conditional diagnosability of interconnection networks. Theor Comput Sci. 2019;757(24):56–67.
   Google Scholar
• Xu X, Li WW, Zhou SM, et al. The g-good-neighbor diagnosability of (n,k)-star graph. Theor Comput Sci. 2017;659:53–63.
   Web of Science ®Google Scholar
• Wang M, Guo Y, Wang S. The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model. Int J Comput Math. 2017;94(3):620–631.
   Web of Science ®Google Scholar
• Wang SY, Han WP. The g-good-neighbor conditional diagnosability of n-dimensional hypercubes under the MM* model. Inform Process Lett. 2016;116:574–577.
   Web of Science ®Google Scholar
• Wang S, Wang M. The g-good-neighbor and g-extra diagnosability of networks. Theor Comput Sci. 2019;773(14):107–114.
   Google Scholar
• Cheng D. A relationship between g-good-neighbour conditional diagnosability and g-good-neighbour connectivity in regular graphs. Int J Comput Math: Computer Syst Theory. 2018;3(1):47–52.
   Google Scholar
• Cheng E, Liptak L, Qiu K, et al. A unified approach to the conditional diagnosability of interconnection networks. J Interconnect Netw. 2013;13(3-4):1250007.
   Google Scholar
• Lin L, Hsieh SY, Chen RQ, et al. The relationship between g-restricted connectivity and g-good-neighbor fault diagnosability of general regular networks. IEEE Trans Reliab. 2018;67(1):285–296.
   Web of Science ®Google Scholar
• Cheng E, Qiu K, Shen Z. Diagnosability problems of the exchanged hypercube and its generalization. Int J Comput Math: Computer Syst Theory. 2017;2(1):39–52.
   Google Scholar
• Gu MM, Hao RX, Yang DX. A short note on the 1, 2-good-neighbor diagnosability of balanced hypercubes. J Interconnect Netw. 2016;16(2):1650001.
   Web of Science ®Google Scholar
• Cheng E, Qiu K, Shen Z. On the restricted connectivity of the arrangement graphs. J Supercomput. 2017;73:3669–3682.
   Web of Science ®Google Scholar
• Yuan A, Cheng E, Liptak L. Linearly many faults in (n,k)-star graphs. Int J Found Comput Sci. 2011;22(7):1729–1745.
   Web of Science ®Google Scholar
• Cheng E, Lipták L, Yuan A. Linearly many faults in arrangement graphs. Networks. 2013;61:281–289.
   Web of Science ®Google Scholar
• Lin L, Zhou S, Xu L, et al. Conditional diagnosability of arrangement graphs under the PMC model. Theor Comput Sci. 2014;548:79–97.
   Web of Science ®Google Scholar
• Day K, Tripathi A. A comparative study of topological properties of hypercubes and star graphs. IEEE Trans Parallel Distrib Syst. 1994;5(1):31–38.
   Web of Science ®Google Scholar
• Li XJ, Xu JM. fault-tolerant of (n,k)-star networks. Appl Math Comput. 2014;248(1):525–530.
   Google Scholar
• Hayes JP, Mudge TN, Stout QF, et al. Architecture of a hypercube supercomputer. In: Proceedings of 1986 International Conference on Parallel Processing. 1986. p. 653–660.
   Google Scholar
• Hillis WD. The connection machine. Cambridge: MIT Press; 1985.
   Google Scholar
• Guo C, Lu G, Wu H, et al. Bcube: a high performance, server-centric network architecture for modular data centers. In: Proceedings of IGCOMM09 Barcelona; August 17–21. Spain: ACM; 2009. p. 63–74.
   Google Scholar
• Liu AX, Wang SY, Yuan J, et al. On g-extra conditional diagnosability of hypercubes and folded hypercubes. Theor Comput Sci. 2017;704(15):62–73.
   Google Scholar
• Zhu X, Zhang X. The h-extra conditional diagnosability of hypercubes under the PMC model and MM* model. Int J Comput Math: Computer Syst Theory. 2016;1(3-4):141–150.
   Google Scholar
• Cheng E, Qiu K, Shen Z. A strong connectivity property of the generalized exchanged hypercube. Discrete Appl Math. 2017;216:529–536.
   Web of Science ®Google Scholar
• Yang X, Evans DJ, Megson GM. On the maximal connected component of a hypercube with faulty vertices III. Int J Comput Math. 2006;83(1):27–37.
   Web of Science ®Google Scholar
• Yang W, Meng J. Extraconnectivity of hypercubes. Appl Math Lett. 2009;22:887–891.
   Web of Science ®Google Scholar
• Zhu Q, Ma F, Guo G, et al. From graph isoperimetric inequality to network connectivity – a new approach. arXiv:1607.07761, 2016.
   Google Scholar
• Kiasari AE, Sarbazi-Azad H. Analytic performance comparison of hypercubes and star graphs with implementation constraints. J Comput Syst Sci. 2008;74:1000–1012.
   Web of Science ®Google Scholar
• Yang W, Li H, Guo X. A kind of conditional fault tolerance of (n,k)-star graphs. Inform Process Lett. 2010;110:1007–1011.
   Web of Science ®Google Scholar
• Cheng E, Qiu K, Shen Z. A note on the alternating group network. J Supercomput. 2012;59(1):246–248.
   Web of Science ®Google Scholar
• Hsieh SY, Chen G -H. Fault-free Hamiltonian cycles in faulty arrangement graphs. IEEE Trans Parallel Distrib Syst. 1999;10(3):223–237.
   Web of Science ®Google Scholar
• Wang S, Feng K. Fault tolerance in the arrangement graphs. Theor Comput Sci. 2014;533:64–71.
   Web of Science ®Google Scholar
• Zhou S, Xu J-M. Conditional fault tolerance of arrangement graphs. Inform Process Lett. 2011;111:1037–1043.
   Web of Science ®Google Scholar
• Wang S, Ren Y. g-good-neighbor diagnosability of arrangement graphs under the PMC model and MM* model. Information. 2018;9:275. doi:https://doi.org/10.3390/info9110275.
   Google Scholar
• Wang S, Ren Y. Some properties of the g-good-neighbor (g-extra) diagnosability of a multiprocessor system. Amer J Comput Math. 2016;6:259–266.
   Google Scholar
• Jwo JS, Lakshmivarahan S, Dhall SK. A new class of interconnection networks based on the alternating group. Networks. 1993;23:315–326.
   Web of Science ®Google Scholar