The g-extra conditional diagnosability and sequential t/k-diagnosability of hypercubes

References

• T. Araki and Y. Shibata, (t,k)-diagnosable system: A generalization of the PMC models, Trans. Comput. 52(7) (2003), pp. 971–975. doi: 10.1109/TC.2003.1214345
   Web of Science ®Google Scholar
• J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, New York, 2007.
   Google Scholar
• G.-Y. Chang, Conditional (t,k)-diagnosis under the PMC model, IEEE Trans. Parallel Distrib. Syst. 22(11) (2011), pp. 1797–1803. doi: 10.1109/TPDS.2011.84
   Web of Science ®Google Scholar
• G.-Y. Chang, G.-H. Chen, and G.J. Chang, (t,k)-diagnosis for matching composition networks, IEEE Trans. Comput. 55(1) (2006), pp. 88–92. doi: 10.1109/TC.2006.1
   Web of Science ®Google Scholar
• G.-Y. Chang, G.-H. Chen, and G.J. Chang, (t,k)-diagnosis for matching composition networks under the MM* model, IEEE Trans. Comput. 56(1) (2007), pp. 73–79. doi: 10.1109/TC.2007.250624
   Web of Science ®Google Scholar
• K.-Y. Chwa and S.L. Hakimi, On fault identification in diagnosable systems, IEEE Trans. Comput. 30(6) (1981), pp. 414–422. doi: 10.1109/TC.1981.1675807
   Web of Science ®Google Scholar
• C.-A. Chen and S.-Y. Hsieh, (t,k)-diagnosis for component-composition graphs under the MM* model, IEEE Trans. Comput. 60(12) (2011), pp. 1704–1717. doi: 10.1109/TC.2010.201
   Web of Science ®Google Scholar
• N.-W. Chang and S.-Y. Hsieh, Conditional diagnosability of augmented cubes under the PMC model, IEEE Trans. Dependable Secur. Comput. 9(1) (2012), pp. 46–60. doi: 10.1109/TDSC.2010.59
   Web of Science ®Google Scholar
• C.-A. Chen and S.-Y. Hsieh, Component-composition graphs: (t,k)-Diagnosability and its application, IEEE Trans. Comput. 62(6) (2013), pp. 1097–1110. doi: 10.1109/TC.2012.58
   Web of Science ®Google Scholar
• C.-F. Chiang, G.-H. Hsu, L.-M. Shih, and J.J.M. Tan, Diagnosability of star graphs with missing edges, Inf. Sci. 188 (2012), pp. 253–259. doi: 10.1016/j.ins.2011.11.012
   Web of Science ®Google Scholar
• E. Cheng and L. Lipták, Diagnosability of Cayley graphs generated by transposition trees with missing edges, Inf. Sci. 238 (2013), pp. 250–252. doi: 10.1016/j.ins.2013.03.009
   Web of Science ®Google Scholar
• N.-W. Chang, T.-Y. Lin, and S.-Y. Hsieh, Conditional diagnosability of k-Ary n-cubes under the PMC model, ACM Trans. Des. Autom. Electron. Syst. 17(4) (2012), pp. 1–14. doi: 10.1145/2348839.2348850
   Web of Science ®Google Scholar
• E. Cheng, L. Lipták, K. Qiu, and Z. Shen, A unified approach to the conditional diagnosability of interconnection networks, J. Interconnect. Netw. 13 (2012), p. 1250007. doi:10.1142/S0219265912500077.
   Google Scholar
• E. Cheng, L. Lipták, K. Qiu, and Z. Shen, On deriving conditional diagnosability of interconnection networks, Inf. Process. Lett. 112(17–18) (2012), pp. 674–677. doi: 10.1016/j.ipl.2012.06.008
   Web of Science ®Google Scholar
• E. Cheng, L. Lipták, and D.E. Steffy, Strong local diagnosability of (n,k)-star graphs and Cayley graphs generated by 2-trees with missing edges, Inf. Process. Lett. 113(12) (2013), pp. 452–456. doi: 10.1016/j.ipl.2013.03.002
   Web of Science ®Google Scholar
• E. Cheng, K. Qiu, and Z. Shen, On the conditional diagnosability of matching composition networks, Theor. Comput. Sci. 557 (2014), pp. 101–114. doi: 10.1016/j.tcs.2014.09.008
   Web of Science ®Google Scholar
• A.T. Dahbura and G.M. Masson, An O(n2.5) faulty identification algorithm for diagnosable systems, IEEE Trans. Comput. 33(6) (1984), pp. 486–492. doi: 10.1109/TC.1984.1676472
   Web of Science ®Google Scholar
• E.P. Duarte Jr., R.P. Ziwich, and L.C. P. Albini, A Survey of comparison-based system-level diagnosis, ACM Comput. Surv. 43(3) (2011), article 22. doi: 10.1145/1922649.1922659
   Web of Science ®Google Scholar
• J. Fan, Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Trans. Parallel Distrib. Syst. 13(7) (2002), pp. 687–692. doi: 10.1109/TPDS.2002.1019858
   Web of Science ®Google Scholar
• J. Fàbrega and M.A. Fiol, On the extraconnectivity of graphs, Discrete Math. 155 (1996), pp. 49–57. doi: 10.1016/0012-365X(94)00369-T
   Web of Science ®Google Scholar
• J. Fan and X. Lin, The t/k-diagnosability of the BC graphs, IEEE Trans. Comput. 54(2) (2005), pp. 176–184. doi: 10.1109/TC.2005.33
   Web of Science ®Google Scholar
• G.-H. Hsu, C.-F. Chiang, L.-M. Shih, L.-H. Hsu, and J.J.M. Tan, Conditional diagnosability of hypercubes under the comparison diagnosis model, J. Syst. Archit. 55(2) (2009), pp. 140–146. doi: 10.1016/j.sysarc.2008.10.005
   Web of Science ®Google Scholar
• W.-S. Hong and S.-Y. Hsieh, Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model, IEEE Trans. Reliab. 61(1) (2012), pp. 140–148. doi: 10.1109/TR.2011.2170105
   Web of Science ®Google Scholar
• S.-Y. Hsieh and C.-Y. Kao, The conditional diagnosability of k-Ary n-cubes under the comparison diagnosis model, IEEE Trans. Comput. 62(4) (2013), pp. 839–843. doi: 10.1109/TC.2012.18
   Web of Science ®Google Scholar
• G.-H. Hsu and J.J.M. Tan, A local diagnosability measure for multiprocessor systems, IEEE Trans. Parallel Distrib. Syst. 18(5) (2007), pp. 598–607. doi: 10.1109/TPDS.2007.1022
   Web of Science ®Google Scholar
• S.-Y. Hsieh, C.-Y. Tsai, and C.-A. Chen, Strong diagnosability and conditional diagnosability of multiprocessor systems and folded hypercubes, IEEE Trans. Comput. 62(7) (2013), pp. 1472–1477. doi: 10.1109/TC.2012.110
   Web of Science ®Google Scholar
• A. Kavianpour, Sequential diagnosability of star graphs, Comput. Electr. Eng. 22(1) (1996), pp. 37–44. doi: 10.1016/0045-7906(95)00028-3
   Web of Science ®Google Scholar
• H.-C. Kim, H.-S. Lim, and J.-H. Park, An approach to conditional diagnosability analysis under the PMC model and its application to torus networks, Theor. Comput. Sci. 548 (2014), pp. 98–116. doi: 10.1016/j.tcs.2014.07.006
   Web of Science ®Google Scholar
• P.-L. Lai, J.J.M. Tan, C.-P. Chang, and L.-H. Hsu, Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput. 54(2) (2005), pp. 165–175. doi: 10.1109/TC.2005.19
   Web of Science ®Google Scholar
• X. Li, X. Yang, L. He, J. Zhang, and C. Yu, Conditional diagnosability of optical multi-mesh hypercube networks under the comparison diagnosis model, Theor. Comput. Sci. 531(24) (2014), pp. 47–53. doi: 10.1016/j.tcs.2014.02.016
   Web of Science ®Google Scholar
• C.-K. Lin, J.J.M. Tan, L.-H. Hsu, E. Cheng, and L. Lipták, Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model, J. Interconnect. Netw. 9 (2008), pp. 83–97. doi: 10.1142/S0219265908002175
   Google Scholar
• D. Liu and J. Li, Many-to-many n-disjoint path covers in n-dimensional hypercubes, Information Processing Letters 110(14–15) (2010), pp. 580–584. doi: 10.1016/j.ipl.2010.05.004
   Web of Science ®Google Scholar
• J. Maeng and M. Malek, A comparison connection assignment for self-diagnosis of multiprocessor systems, Proceeding of 11th International Symposium on Fault-Tolerant Computing, Portland, Maine, 1981, pp. 173–175.
   Google Scholar
• F.P. Preparata, G. Metze, and R.T. Chien, On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput. EC-16(6) (1967), pp. 848–854. doi: 10.1109/PGEC.1967.264748
   Web of Science ®Google Scholar
• A. Sengupta and A.T. Dahbura, On self-diagnosable multiprocessor system: Diagnosis by the comparison approach, IEEE Trans. Comput. 41(11) (1992), pp. 1386–1396. doi: 10.1109/12.177309
   Web of Science ®Google Scholar
• A.K. Somani and O. Peleg, On diagnosability of large fault sets in regular topology-based computer systems, IEEE Trans. Comput. 45(8) (1996), pp. 892–903. doi: 10.1109/12.536232
   Web of Science ®Google Scholar
• I.A. Stewart, A general technique to establish the asymptotic conditional diagnosability of interconnection networks, Theor. Comput. Sci. 452 (2012), pp. 132–147. doi: 10.1016/j.tcs.2012.05.015
   Web of Science ®Google Scholar
• M. Xu, K. Thulasiraman, and X.-D. Hu, Conditional diagnosability of matching composition networks under the PMC model, IEEE Trans. Circuits Syst. 56(11) (2009), pp. 875–879. doi: 10.1109/TCSII.2009.2030361
   Google Scholar
• X. Yang, A linear time fault diagnosis algorithm for hypercube multiprocessors under the MM* comparison model, Proceeding of the 12th Asian Test Symposium (ATS'03), Xian, China, 2003, pp. 50–55.
   Google Scholar
• M.-C. Yang, Conditional diagnosability of matching composition networks under the MM* model, Inf. Sci. 233(1) (2013), pp. 230–243. doi: 10.1016/j.ins.2013.01.019
   Web of Science ®Google Scholar
• W. Yang, H. Lin, and C. Qin, On the t/k-diagnosability of BC networks, Appl. Math. Comput. 225(1) (2013), pp. 366–371. doi: 10.1016/j.amc.2013.09.063
   Web of Science ®Google Scholar
• W. Yang and J. Meng, Extraconnectivity of hypercubes, Appl. Math. Lett. 22 (2009), pp. 887–891. doi: 10.1016/j.aml.2008.07.016
   Web of Science ®Google Scholar
• X. Yang and Y.Y. Tang, A (4n−9)/3 diagnosis algorithm on n-dimensional cube network, Inf. Sci. 177(8) (2007), pp. 1771–1781. doi: 10.1016/j.ins.2006.10.002
   Web of Science ®Google Scholar
• T.-L. Ye and S.-Y. Hsieh, A scalable comparison-based diagnosis algorithm for hypercube-like networks, IEEE Trans. Reliab. 62(4) (2013), pp. 789–799. doi: 10.1109/TR.2013.2284743
   Web of Science ®Google Scholar
• J. Yuan, A. Liu, X. Ma, X. Liu, X. Qin, and J. Zhang, The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM* model, IEEE Trans. Parallel Distrib. Syst. (2014). doi:10.1109/TPDS.2014.2318305.
   PubMed Web of Science ®Google Scholar
• S. Zhou, L. Lin, L. Xu, and D. Wang, The t/k-diagnosability of star graph networks, IEEE Trans. Comput. (2013). doi:10.1109/TC.2013.228.
   Web of Science ®Google Scholar
• Q. Zhu, G. Guo, and D. Wang, Relating diagnosability, strong diagnosability and conditional diagnosability of strong networks, IEEE Trans. Comput. 63(7) (2014), pp. 1847–1851. doi: 10.1109/TC.2013.64
   Web of Science ®Google Scholar