
[1] S. B. Akers, D. Horel, and B. Krishnamurthy, The star graph: an attractive alternative to the ncube," International Conference on Parallel Processing, pp. 1249{1268, 1987. [2] S. B. Akers and B. Krishnamurthy, A grouptheoretic model for symmetric in terconnection networks," IEEE Transactions on Computers, vol. 38, no. 4, pp. 555{566, 1989. [3] F. J. Allan, T. Kameda and S. Toida, Approach to the diagnosability analysis of a system," IEEE Transaction on Computers, vol. 25, pp. 1040{1042, 1975. [4] T. Araki and Y. Shibata, Diagnosability of networks by the cartesian product," IEICE Transactions on Fundamentals of Electronics Communications and Com puter Science, vol. 83, no. 3, pp. 465{470, 2000. [5] T. Araki and Y. Shibata, Diagnosability of butter°y networks under the com parison approach," IEICE Transactions on Fundamentals of Electronics Commu nications and Computer Science, vol. E85A, no. 5, pp. 1152{1160, 2002. [6] T. Araki and Y. Shibata, (t; k)Diagnosable system: a generalization of the PMC models," IEEE Transactions on Computers, vol. 52, no. 7, pp. 971{975, 2003. [7] J. R. Armstrong and F. G. Gray, Fault diagnosis in a boolean ncube array of microprocessors," IEEE Transactions on Computers, vol. 30, no. 8, pp. 587{590, 1981. 51 [8] M. Asim, H. Mokhtar, and M. Merabti, A cellular approach to fault detection and recovery in wireless sensor networks," in Proceedings of the Third International Conference on Sensor Technologies and Applications (SENSORCOMM'09), pp. 352{357, 2009. [9] F. Barsi, F. Grandoni and P. Maestrini, A theory of diagnosability in digital systems," IEEE Transactions on Computers, vol. 25, pp. 585{593, 1976. [10] E. R. Berlekamp, Algebraic Coding Theory, (revised), Aegean Park Press, Laguna Hills, 1984. [11] P. Berman and A. Pelc, Distributed probabilistic fault diagnosis for multiproces sor systems," Proceeding of IEEE Computer Society 20th International Symposium of FaultTolerant Computing, pp. 340{346, 1990. [12] D. M. Blough, G. F. Sullivan and G. M. Masson, Almost certain diagnosis for in termittently faulty systems," Proceeding of IEEE CS 18th International Sympsium on FaultTolerant Computing, pp. 260{265, 1988. [13] D. M. Blough, G. F. Sullivan, and G. M. Masson, Fault diagnosis for sparsely interconnected multiprocessor systems," Proceeding of IEEE Computer Society 19th International Sympsium on FaultTolerant Computing, pp. 62{69, 1989. [14] D. M. Blough and A. Pelc, Reliable diagnosis and repair in constantdegree mul tiprocessor systems," Proceeding of IEEE Computer Society 20th International Sympsium on FaultTolerant Computing, pp. 316{323, 1990. [15] D. M. Blough, G. F. Sullivan and G. M. Masson, E±cient diagnosis of multi processor systems under probabilistic models," IEEE Transactions on Computers, vol. 41, pp. 1126{1136, 1992. [16] D. M. Blough, G. F. Sullivan and G. M. Masson, Intermittent fault diagnosis in multiprocessor system," IEEE Transactions on Computers, vol. 41, pp. 1430{1441, 52 1992. [17] G. Y. Chang, G. J. Chang, and G. H. Chen, Diagnosabilities of regular networks," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 4, pp. 314{ 322, 2005. [18] G. Y. Chang, G. H. Chen, and G. J. Chang, (t; k)Diagnosis for matching com position networks," IEEE Transactions on Computers, vol. 55, no. 1, pp. 88{92, 2006. [19] G. Y. Chang and G. H. Chen, (t; k)Diagnosability of multiprocessor systems with applications to grids and tori," SIAM Journal on Computing, vol. 37, no. 4, pp. 1280{1298, 2007. [20] G. Y. Chang, G. H. Chen, and G. J. Chang, (t; k)Diagnosis for matching com position networks under the MM* model," IEEE Transactions on Computers, vol. 56, no. 1, pp. 73{79, 2007. [21] G. Y. Chang, Conditional (t; k)Diagnosis under the PMC Model," IEEE Trans actions on Parallel and Distributed Systems, vol. 22, no. 11, pp. 1797{1803, 2011. [22] C. A. Chen and S. Y. Hsieh (t; k)Diagnosis For ComponentComposition Graphs Under the MM* Model," IEEE Transactions on Computers, vol. 60, no. 12, pp. 1704{1717, 2011. [23] C. A. Chen and S. Y. Hsieh, Componentcomposition graphs: (t,k)diagnosability and its application," IEEE Transactions on Computers, vol. 62, no. 2, pp. 1097{ 1110, 2013. [24] C. A. Chen, G. Y. Chang and S. Y. Hsieh, Conditional (t; k)diagnosis in graphs by using the comparison diagnosis model," IEEE Transactions on Computers, vol. 64, no. 6, pp. 16221632, June 2015. 53 [25] A. Caruso, S. Chessa, P. Maestrini, and P. Santi, Diagnosability of Regular Sys tems," J. Algorithms, vol. 1, no. 1, pp. 1{12, 2002. [26] S. Chessa and P. Santi, Crash faults identi¯cation in wireless sensor networks," Computer Communications, vol. 25, no. 14, pp. 12731282, 2002. [27] S. A. Choudum and V. Sunitha, Augmented cubes," Networks, vol. 40, no. 2, pp. 71{84, 2002. [28] K. Y. Chwa and S. L. Hakimi, On fault identi¯cation in diagnosable systems," IEEE Transactions on Computers, vol. 30, no. 6, pp. 414{422, 1981. [29] K. Y. Chwa and S. L. Hakimi, Schemes for fault tolerant computing: a compari son of modularly redundant and tdiagnosable systems," Information and Control, vol. 49, pp. 212{238, 1981. [30] P. Cull and S.M. Larson, The MÄobius cubes," IEEE Transactions on Computers, vol. 44, no. 5, pp. 647{659, May 1995. [31] A. T. Dahabura and G. M. Masson, An O(n2:5) fault identi¯cation algorithm for diagnosable systems," IEEE Transactions on Computers, vol. C33, no. 6, pp. 486{492, 1984. [32] A. T. Dahbura, Systemlevel diagnosis: a perspective for the third decade," Concurrent Computation: Algorithms, Arhcitectures, Technologies. New York: Plenum 1988. [33] A. T. Dahabura and G. M. Masson, Improved diagnosability algorithm," IEEE Transactions on Computers, vol. 40, no. 2, pp. 143{153, 1991. [34] A. Das, K. Thulasiraman, V. K. Agarwal and K. B. Lakshmanan, Multiprocessor fault diagnosis under local constraints," IEEE Transactions on Computers, vol. 42, no. 8, pp. 984{988, 1993. 54 [35] A. ElAmawy, S. Lati¯, Properties and performance of folded hypercubes," IEEE Transactions on Parallel and Distributed Systems, vol. 2, no. 1, pp. 31{42, 1991. [36] K. Efe, A variation on the hypercube with lower diameter," IEEE Transactions on Computers, vol. 40, no. 11, pp. 1312{1316, Nov. 1991. [37] A. H. Esfahanian, Generalized measures of fault tolerance with application to N cube networks, IEEE Transactions on Computers, vol. 38, no. 11, pp. 1586{1591, 1989. [38] J. Fan, Diagnosability of the mÄobius cubes," IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 9, pp. 923{928, 1998. [39] J. Fan, Diagnosability of crossed cubes under the comparison diagnosis model," IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 7, pp. 687{ 692, 2002. [40] J. Fan and X. Lin, The t=kdiagnosability of the BC graphs," IEEE Transactions on Computers, vol. 54, no. 2, pp. 176{184, 2005. [41] W. Feller, Stirling's formula," in: An Introduction to Probability Theory and Its Applications, 3rd Edition, vol. 1, Wiley, New York, pp. 50{53, 1968 (chapter 2.9). [42] A. D. Friedman and L. Simoncini, Systemlevel fault diagnosis," Computer, vol. 13, no. 3, pp. 47{53, 1980. [43] H. Fujiwara and K. Kinoshita, On the computational complexity of system diag nosis," IEEE Transactions on Computers, vol. C27, no. 10, pp. 881{885, 1978. [44] A. Ghafoor, A class of faulttolerant multiprocessor networks," IEEE Transac tions on Reliability, vol. 38, no. 1, pp. 5{15, 1989. [45] A. Ghafoor, Partitioning of even networks for improved diagnosability," IEEE Transactions on Reliability, vol. 39, no. 3, pp. 281{286, 1990. 55 [46] S. L. Hakimi and A. T. Amin, On the computational complexity of system diag nosis," IEEE Transactions on Computers, vol. 23, no. 1, pp. 86{88, 1974. [47] F. Harary, M. Livingston, Independent domination in hypercubes," Applied mathematics letters, vol. 6, pp. 27{28, 1993. [48] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. va_a de Snepscheut, The twisted cubes," Proc. Parallel Architecture and Language Europe, pp. 152{159, June 1987. [49] W. S. Hong and S. Y. Hsieh, Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model," IEEE Transactions on Reliability, vol. 61, no. 1, pp. 140{148, March 2012. [50] S. H. Hosseini, J. G. Kuhl and S. M. Reddy, Diagnosis algorithm for distributed computing systems," IEEE Transactions on Computers, vol. 33, pp. 223233, 1984. [51] S. Y. Hsieh and Y. S. Chen, Strongly diagnosable product networks under the comparison diagnosis model," IEEE Transactions on Computers, vol. 57, no. 6, pp. 721{731, 2008. [52] J. Hwang, T. He, and Y. Kim, Secure localization with phantom node detection," Ad Hoc Networks, vol. 6, no. 7, pp. 1031{1050, 2008. [53] Y. Ishida, N. Adachi, and H. Tokumaru, Diagnosability and distinguishability analysis and its applications," IEEE Transactions on Reliability, vol. 36, no. 5, pp. 531{538, 1987. [54] A. Kavianpour and K. H. Kim, Diagnosabilities of hypercubes under the pes simistic onestep diagnosis strategy," IEEE Transactions on Computers, vol. 40, no. 2, pp. 232{237, 1991. [55] A. Kavianpour and K. H. Kim, A comparative evaluation of four basic system level diagnosis strategies for hypercubes," IEEE Transactions on Reliability, vol. 41, no. 1, pp. 26{37, 1992. 56 [56] A. Kavianpour and K. H. Kim, A comparative evaluation of four basic system level diagnosis strategies for hypercubes," IEEE Transactions on Computers, vol. 41, no. 1, pp. 26{37, 1992. [57] A. Kavianpour, Sequential diagnosability of star graphs," Computers & Electrical Engineering, vol. 22, no. 1, pp. 37{44, 1996. [58] S. Khanna and W. K. Fuchs, A linear time algorithm for sequential diagnosis in hypercubes," Journal of Parallel and Distributed Computing, vol. 26, pp. 48{53, 1995. [59] S. Khanna and W. K. Fuchs, A graph partitioning approach to sequential diag nosis," IEEE Transactions on Computers, vol. 46, no. 1, pp. 39{47, 1997. [60] J. G. Kuhl and S. M. Reddy, Fault diagnosis in fully distributed systems," Proceedings of IEEE Computer Society 11th International Sympsium on Fault Tolerant Computing, pp. 100{105, 1981. [61] S. P. Kuo, H. J. Kuo, and Y. C. Tseng, The beacon movement detection problem in wireless sensor networks for localization applications," IEEE Transactions on Mobile Computing, vol. 8, no. 10, pp. 1326{1338, Oct. 2009. [62] C. L. Kuo, M. J. Yang, Y. M. Chang, and Y. M. Yeh, High diagnosability of a sequential diagnosis algorithm in hypercubes under the PMC model," Journal of Supercomputing, vol. 61, no. 3, pp. 1116{1134, Sep. 2012. [63] P. L. Lai, J. M. Tan, C. P. Chang, and L. H. Hsu, Conditional diagnosability measures for large multiprocessor systems," IEEE Transactions on Computers, vol. 54, no. 2, pp. 165{175, Feb. 2005. [64] P. L. Lai, J. J. M. Tan, C. H. Tsai, and L. H. Hsu, The diagnosability of the matching composition network under the comparison diagnosis model," IEEE Transactions on Computers, vol. 53, no. 8, pp. 1064{1069, 2004. 57 [65] P. L. Lai, A systematic algorithm for identifying faults on hypercubelike net works under the comparison model," IEEE Transactions on Reliability, vol. 61, no. 2, pp. 452{459, Jun. 2012. [66] P. L. Lai, M. Y. Chiu, and C. H. Tsai, Three round adaptive diagnosis in hier archical multiprocessor systems," IEEE Transactions on Reliability, vol. 62 , no. 3, pp. 608{617, Sep. 2013. [67] X. J. Li, and J. M. Xu, Generalized measures of fault tolerance in exchanged hypercubes," Information Processing Letters, vol. 113, no. 14{16, pp. 533{537, July 2013. [68] C. K. Lin, J. J. M. Tan, L. H. Hsu, E. Cheng, and L. Lipt¶ak, Conditional diagnos ability of Cayley graphs generated by transposition trees under the comparison diagnosis model," Journal of Interconnection Networks, vol. 9, no. 1 & 2, pp. 83{97, 2008. [69] C. K. Lin, Y. H. Teng, J. J. M. Tan, and L. H. Hsu, Local diagnosis algorithms for multiprocessor systems under the comparison diagnosis model," IEEE Trans actions on Reliability, vol. 62, no. 4, pp. 800{810, Dec. 2013. [70] P. K. K. Loh, W. J. Hsu, and Y. Pan, The exchanged hypercube," IEEE Trans actions on Parallel and Distributed Systems, vol. 16, no. 9, pp. 866{874, 2005. [71] M. Ma, G. Liu, and J. M. Xu, The super connectivity of augmented cubes," Information Processing Letters vol. 106, pp. 59{63, 2008. [72] S. Mallela and G. M. Masson, Diagnosable systems for intermittent fault," IEEE Transactions on Computers, vol. 27, pp. 460{470, 1978. [73] M. Ma, and L. Zhu, The super connectivity of exchanged hypercubes," Informa tion Processing Letters vol. 111, pp. 360{364, 2011. 58 [74] M. Malek, A comparison connection assignment for diagnosable of multiproces sor systems," in Proceedings of the 7th International Symposium on Computer Architecture, pp. 31{36, 1980. [75] J. Maeng and M. Malek, A comparison connection assignment for selfdiagnosis of multiprocessor systems," in Proceeding 11th International Symposium on Fault Tolerant Computing, pp. 173{175, 1981. [76] G. G. L. Meyer, A fault diagnosis algorithm for asymmetric modular architec tures," IEEE Transactions on Computers, vol. 30, pp.81{83, 1981. [77] A. Pelc, Undirected graph models for systemlevel fault diagnosis," IEEE Trans actions on Computers, vol. 40, pp. 1271{1276, 1991. [78] F. P. Preparata, G. Metze, and R. T. Chien, On the connection assignment problem of diagnosable systems," IEEE Transactions on Electronic Computers, vol. EC16, no. 6, pp. 848{854, 1967. [79] Q. Zhu, J.M. Xu, Hou, M. Xu, On reliability of the folded hypercubes," Infor mation Sciences: An international Journal, vol. 177, no. 8, pp. 1782{1788, 2007. [80] H. Robbins, A remark of Stirling's formula," American Mathematical Monthly, vol. 62, pp. 26{29, 1955. [81] J. D. Russell and C. R. Kime, System fault diagnosis: masking, exposure, and diagnosability without repair," IEEE Transactions on Computers, vol. C24, PP. 1156{1161, 1975. [82] Y. Saad and M.H. Schultz, Topological properties of hypercubes," IEEE Trans actions on Computers, vol. 37, no. 7, pp. 867{872, July 1988. [83] A. Sengupta and A. T. Danbura, On selfdiagnosable multiprocessor systems: diagnosis by the comparison approach," IEEE Transactions on Computers, vol. 41, no. 11, pp. 1386{1396, 1992. 59 [84] A. K. Somani, V. K. Agarwal and D. Avis, A generalized theory for system level diagnosis," IEEE Transactions on Computers, vol. C36, no. 5, pp. 538{546, 1987. [85] A. K. Somani and V. K. Agarwal, Distributed syndrome decoding for regular in terconnected structure," Proceeding of IEEE Computer Society 19th International Sympsium on FaultTolerant Computing, pp. 70{77, 1989. [86] A. K. Somani, V. K. Agarwal and D. Avis, On the complexity of single fault set diagnosability and diagnosis problems," IEEE Transactions on Computers, vol. 38, pp. 195{201, 1989. [87] A. K. Somani and O. Peleg, On diagnosability of large fault sets in regular topologybased computer systems," IEEE Transactions on Computers, vol. 45, no. 8, pp. 892{902, 1996. [88] G. Sullivan, A polynomial time algorithm for fault diagnosability," Proceedings of the 11th Annual Symposium on Computer Architecture, pp. 148{156, 1984. [89] G. Sullivan, An O(t3+jEj) fault identi¯cation algorithm for diagnosable systems," IEEE Transactions on Computers, vol. 37, pp. 388{397, 1988. [90] T.M. Thompson, From errorcorrecting codes through sphere packings to simple groups," Mathematical Association of America, Washington, 1983. [91] G. J. M. vanWee, Improved sphere bounds on the covering radius of codes," IEEE Transactions on Information Theory, vol. 34, no. 2, pp. 237{245, Mar. 1988. [92] D. Wang, Diagnosability of enhanced hypercubes," IEEE Transactions on Com puters, vol. 43, no. 9, pp. 1054{1061, 1994. [93] D. B.West: Introduction to Graph Theory (Second Edition), Prentice Hall, Upper Saddle River. (2001) 60 [94] D. Wang, Diagnosability of hypercubes and enhanced hypercubes under the com parison diagnosis model," IEEE Transactions on Computers, vol. 48, no. 12, pp. 1369{1374, 1999. [95] J. Wu, K. Huang, The balanced hypercube: a cubebased system for fault tolerant applications," IEEE Transactions on Computers, vol. 46, no. 4, pp. 484{ 490, 1997. [96] J. Xu and S. Z. Huang, Sequentially tdiagnosable system: a characterization and its applications," IEEE Transactions on Computers, vol. 44, no. 2, pp. 340{345, 1995. [97] J. M. Xu, Q. Zhu, X. M. Hou and T. Zhou, On restricted connectivity and extra connectivity of hypercubes and folded hypercubes,"J. Shanghai Jiaotong Univ. (Sci.) E10, no. 2, pp. 208{212, 2005. [98] M. C. Yang, Super connectivity of balanced hypercubes," Applied Mathematics and Computation, vol. 219, no. 3, pp. 970{975, 2012. [99] X. Yang, A linear time fault diagnosis algorithm for hypercube multiprocessors under the MM* comparison model," in: Proceedings of the 12th Asian Test Sym posium, pp. 50{57, 2003. [100] T. L. Ye and S. Y. Hsieh, A scalable comparisonbased diagnosis algorithm for hypercubelike networks," IEEE Transactions on Reliability, vol. 62, number 4, pp. 789{799, Dec. 2013. [101] T. Yamada, T. Ohtsukab, A. Watanabe, and S. Ueno, On sequential diagnosis of multiprocessor systems," Discrete Applied Mathematics, vol. 146, no. 3, pp. 311{342, 2005. [102] J. Zhao, F. J. Meyer, N. Park, and F. Lombardi, Sequential diagnosis of proces sor array systems," IEEE Transactions on Reliability, vol. 53, no. 4, pp. 487{498, 61 2004. [103] J. Zheng, S. Lati¯, E. Regentova, K. Luo, and X. Wu, Diagnosability of star graphs under the comparison diagnosis model," Information Processing Letters, vol. 93, no. 1, pp. 29{36, 2005.
