{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T09:01:30Z","timestamp":1767085290929},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,9,15]],"date-time":"2016-09-15T00:00:00Z","timestamp":1473897600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00453-016-0210-3","type":"journal-article","created":{"date-parts":[[2016,9,15]],"date-time":"2016-09-15T13:53:30Z","timestamp":1473947610000},"page":"625-644","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Random and Conditional (t,\u00a0k)-Diagnosis of Hypercubes"],"prefix":"10.1007","volume":"79","author":[{"given":"Chia-Chen","family":"Wei","sequence":"first","affiliation":[]},{"given":"Sun-Yuan","family":"Hsieh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,15]]},"reference":[{"issue":"3","key":"210_CR1","first-page":"465","volume":"E83\u2013A","author":"T Araki","year":"2000","unstructured":"Araki, T., Shibata, Y.: Diagnosability of networks represented by the cartesian product. IEICE Trans. Fundam. E83\u2013A(3), 465\u2013470 (2000)","journal-title":"IEICE Trans. Fundam."},{"issue":"7","key":"210_CR2","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1109\/TC.2003.1214345","volume":"52","author":"T Araki","year":"2003","unstructured":"Araki, T., Shibata, Y.: $$(t, k)$$ ( t , k ) -Diagnosable system: a generalization of the PMC models. IEEE Trans. Comput. 52(7), 971\u2013975 (2003)","journal-title":"IEEE Trans. Comput."},{"issue":"8","key":"210_CR3","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1109\/TC.1981.1675844","volume":"30","author":"JR Armstrong","year":"1981","unstructured":"Armstrong, J.R., Gray, F.G.: Fault diagnosis in a boolean $$n$$ n cube array of multiprocessors. IEEE Trans. Comput. 30(8), 587\u2013590 (1981)","journal-title":"IEEE Trans. Comput."},{"key":"210_CR4","doi-asserted-by":"crossref","unstructured":"Asim, M., Mokhtar, H., Merabti, M.: A cellular approach to fault detection and recovery in wireless sensor networks. In: Proceedings of the Third International Conference on Sensor Technologies and Applications (SENSOR-COMM\u201909), pp. 352\u2013357. (2009)","DOI":"10.1109\/SENSORCOMM.2009.61"},{"key":"210_CR5","volume-title":"Algebraic Coding Theory (Revised)","author":"ER Berlekamp","year":"1984","unstructured":"Berlekamp, E.R.: Algebraic Coding Theory (Revised). Aegean Park Press, Laguna Hills (1984)"},{"issue":"4","key":"210_CR6","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1109\/TPDS.2005.44","volume":"16","author":"GY Chang","year":"2005","unstructured":"Chang, G.Y., Chang, G.J., Chen, G.H.: Diagnosabilities of regular networks. IEEE Trans. Parallel Distrib. Syst. 16(4), 314\u2013322 (2005)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"1","key":"210_CR7","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1109\/TC.2006.1","volume":"55","author":"GY Chang","year":"2006","unstructured":"Chang, G.Y., Chen, G.H., Chang, G.J.: $$(t, k)$$ ( t , k ) -Diagnosis for matching composition networks. IEEE Trans. Comput. 55(1), 88\u201392 (2006)","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"210_CR8","doi-asserted-by":"crossref","first-page":"1280","DOI":"10.1137\/06065043X","volume":"37","author":"GY Chang","year":"2007","unstructured":"Chang, G.Y., Chen, G.H.: $$(t, k)$$ ( t , k ) -Diagnosability of multiprocessor systems with applications to grids and tori. SIAM J. Comput. 37(4), 1280\u20131298 (2007)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"210_CR9","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1109\/TC.2007.250624","volume":"56","author":"GY Chang","year":"2007","unstructured":"Chang, G.Y., Chen, G.H., Chang, G.J.: $$(t, k)$$ ( t , k ) -Diagnosis for matching composition networks under the MM* model. IEEE Trans. Comput. 56(1), 73\u201379 (2007)","journal-title":"IEEE Trans. Comput."},{"issue":"11","key":"210_CR10","doi-asserted-by":"crossref","first-page":"1797","DOI":"10.1109\/TPDS.2011.84","volume":"22","author":"GY Chang","year":"2011","unstructured":"Chang, G.Y.: Conditional $$(t, k)$$ ( t , k ) -diagnosis under the PMC model. IEEE Trans. Parallel Distrib. Syst. 22(11), 1797\u20131803 (2011)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"12","key":"210_CR11","doi-asserted-by":"crossref","first-page":"1704","DOI":"10.1109\/TC.2010.201","volume":"60","author":"CA Chen","year":"2011","unstructured":"Chen, C.A., Hsieh, S.Y.: $$(t, k)$$ ( t , k ) -Diagnosis for component-composition graphs under the MM* model. IEEE Trans. Comput. 60(12), 1704\u20131717 (2011)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"210_CR12","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1109\/TC.2012.58","volume":"62","author":"CA Chen","year":"2013","unstructured":"Chen, C.A., Hsieh, S.Y.: Component-composition graphs: (t, k)-diagnosability and its application. IEEE Trans. Comput. 62(2), 1097\u20131110 (2013)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"210_CR13","first-page":"1","volume":"1","author":"A Caruso","year":"2002","unstructured":"Caruso, A., Chessa, S., Maestrini, P., Santi, P.: Diagnosability of regular systems. J. Algorithms 1(1), 1\u201312 (2002)","journal-title":"J. Algorithms"},{"issue":"14","key":"210_CR14","doi-asserted-by":"crossref","first-page":"1273","DOI":"10.1016\/S0140-3664(02)00030-0","volume":"25","author":"S Chessa","year":"2002","unstructured":"Chessa, S., Santi, P.: Crash faults identification in wireless sensor networks. Comput. Commun. 25(14), 1273\u20131282 (2002)","journal-title":"Comput. Commun."},{"issue":"6","key":"210_CR15","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1109\/TC.1984.1676472","volume":"C\u201333","author":"AT Dahabura","year":"1984","unstructured":"Dahabura, A.T., Masson, G.M.: An $$O(n^{2.5})$$ O ( n 2.5 ) fault identification algorithm for diagnosable systems. IEEE Trans. Comput. C\u201333(6), 486\u2013492 (1984)","journal-title":"IEEE Trans. Comput."},{"issue":"11","key":"210_CR16","doi-asserted-by":"crossref","first-page":"1586","DOI":"10.1109\/12.42131","volume":"38","author":"AH Esfahanian","year":"1989","unstructured":"Esfahanian, A.H.: Generalized measures of fault tolerance with application to $$N$$ N -cube networks. IEEE Trans. Comput. 38(11), 1586\u20131591 (1989)","journal-title":"IEEE Trans. Comput."},{"issue":"9","key":"210_CR17","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1109\/71.722224","volume":"9","author":"J Fan","year":"1998","unstructured":"Fan, J.: Diagnosability of the M\u00d6bius cubes. IEEE Trans. Parallel Distrib. Syst. 9(9), 923\u2013928 (1998)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"2","key":"210_CR18","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1109\/TC.2005.33","volume":"54","author":"J Fan","year":"2005","unstructured":"Fan, J., Lin, X.: The $$t\/k$$ t \/ k -diagnosability of the BC graphs. IEEE Trans. Comput. 54(2), 176\u2013184 (2005)","journal-title":"IEEE Trans. Comput."},{"key":"210_CR19","unstructured":"Feller, W.: Stirling\u2019s formula. In: An Introduction to Probability Theory and Its Applications, 3rd edn., vol. 1, pp. 50\u201353. John Wiley and Sons, New York (1968) (chapter 2.9)"},{"issue":"10","key":"210_CR20","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1109\/TC.1978.1674966","volume":"27","author":"H Fugiwara","year":"1978","unstructured":"Fugiwara, H., Kinoshita, K.: On the computational complexity of system diagnosis. IEEE Trans. Comput. 27(10), 881\u2013885 (1978)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"210_CR21","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1109\/24.24569","volume":"38","author":"A Ghafoor","year":"1989","unstructured":"Ghafoor, A.: A class of fault-tolerant multiprocessor networks. IEEE Trans. Reliab. 38(1), 5\u201315 (1989)","journal-title":"IEEE Trans. Reliab."},{"issue":"3","key":"210_CR22","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1109\/24.103002","volume":"39","author":"A Ghafoor","year":"1990","unstructured":"Ghafoor, A.: Partitioning of even networks for improved diagnosability. IEEE Trans. Reliab. 39(3), 281\u2013286 (1990)","journal-title":"IEEE Trans. Reliab."},{"key":"210_CR23","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1109\/T-C.1974.223782","volume":"23","author":"SL Hakimi","year":"1974","unstructured":"Hakimi, S.L., Amin, A.T.: Characterization of connection assignment. IEEE Trans. Comput. 23, 86\u201388 (1974)","journal-title":"IEEE Trans. Comput."},{"key":"210_CR24","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0893-9659(93)90027-K","volume":"6","author":"F Harary","year":"1993","unstructured":"Harary, F., Livingston, M.: Independent domination in hypercubes. Appl. Math. Lett. 6, 27\u201328 (1993)","journal-title":"Appl. Math. Lett."},{"issue":"6","key":"210_CR25","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1109\/TC.2008.30","volume":"57","author":"SY Hsieh","year":"2008","unstructured":"Hsieh, S.Y., Chen, Y.S.: Strongly diagnosable product networks under the comparison diagnosis model. IEEE Trans. Comput. 57(6), 721\u2013731 (2008)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"210_CR26","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1109\/TPDS.2008.99","volume":"20","author":"SY Hsieh","year":"2009","unstructured":"Hsieh, S.Y., Chuang, T.Y.: The strong diagnosability of regular networks and product networks under the PMC model. IEEE Trans. Parallel Distrib. Syst. 20(3), 367\u2013378 (2009)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"7","key":"210_CR27","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.1016\/j.adhoc.2007.10.005","volume":"6","author":"J Hwang","year":"2008","unstructured":"Hwang, J., He, T., Kim, Y.: Secure localization with phantom node detection. Ad Hoc Netw. 6(7), 1031\u20131050 (2008)","journal-title":"Ad Hoc Netw."},{"issue":"5","key":"210_CR28","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1109\/TR.1987.5222465","volume":"36","author":"Y Ishida","year":"1987","unstructured":"Ishida, Y., Adachi, N., Tokumaru, H.: Diagnosability and distinguishability analysis and its applications. IEEE Trans. Reliab. 36(5), 531\u2013538 (1987)","journal-title":"IEEE Trans. Reliab."},{"issue":"2","key":"210_CR29","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1109\/12.73595","volume":"40","author":"A Kavianpour","year":"1991","unstructured":"Kavianpour, A., Kim, K.H.: Diagnosabilities of hypercubes under the pessimistic one-step diagnosis strategy. IEEE Trans. Comput. 40(2), 232\u2013237 (1991)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"210_CR30","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/24.126666","volume":"41","author":"A Kavianpour","year":"1992","unstructured":"Kavianpour, A., Kim, K.H.: A comparative evaluation of four basic system-level diagnosis strategies for hypercubes. IEEE Trans. Reliab. 41(1), 26\u201337 (1992)","journal-title":"IEEE Trans. Reliab."},{"issue":"1","key":"210_CR31","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0045-7906(95)00028-3","volume":"22","author":"A Kavianpour","year":"1996","unstructured":"Kavianpour, A.: Sequential diagnosability of star graphs. Comput. Electr. Eng. 22(1), 37\u201344 (1996)","journal-title":"Comput. Electr. Eng."},{"key":"210_CR32","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1006\/jpdc.1995.1046","volume":"26","author":"S Khanna","year":"1995","unstructured":"Khanna, S., Fuchs, W.K.: A linear time algorithm for sequential diagnosis in hypercubes. J. Parallel Distrib. Comput. 26, 48\u201353 (1995)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"1","key":"210_CR33","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1109\/12.559801","volume":"46","author":"S Khanna","year":"1997","unstructured":"Khanna, S., Fuchs, W.K.: A graph partitioning approach to sequential diagnosis. IEEE Trans. Comput. 46(1), 39\u201347 (1997)","journal-title":"IEEE Trans. Comput."},{"issue":"10","key":"210_CR34","doi-asserted-by":"crossref","first-page":"1326","DOI":"10.1109\/TMC.2009.15","volume":"8","author":"SP Kuo","year":"2009","unstructured":"Kuo, S.P., Kuo, H.J., Tseng, Y.C.: The beacon movement detection problem in wireless sensor networks for localization applications. IEEE Trans. Mob. Comput. 8(10), 1326\u20131338 (2009)","journal-title":"IEEE Trans. Mob. Comput."},{"issue":"3","key":"210_CR35","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1007\/s11227-011-0688-z","volume":"61","author":"CL Kuo","year":"2012","unstructured":"Kuo, C.L., Yang, M.J., Chang, Y.M., Yeh, Y.M.: High diagnosability of a sequential diagnosis algorithm in hypercubes under the PMC model. J. Supercomput. 61(3), 1116\u20131134 (2012)","journal-title":"J. Supercomput."},{"issue":"2","key":"210_CR36","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/TC.2005.19","volume":"54","author":"PL Lai","year":"2005","unstructured":"Lai, P.L., Tan, J.M., Chang, C.P., Hsu, L.H.: Conditional diagnosability measures for large multiprocessor systems. IEEE Trans. Comput. 54(2), 165\u2013175 (2005)","journal-title":"IEEE Trans. Comput."},{"issue":"8","key":"210_CR37","doi-asserted-by":"crossref","first-page":"1064","DOI":"10.1109\/TC.2004.50","volume":"53","author":"PL Lai","year":"2004","unstructured":"Lai, P.L., Tan, J.J.M., Tsai, C.H., Hsu, L.H.: The diagnosability of the matching composition network under the comparison diagnosis model. IEEE Trans. Comput. 53(8), 1064\u20131069 (2004)","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"210_CR38","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1109\/TR.2013.2285031","volume":"62","author":"CK Lin","year":"2013","unstructured":"Lin, C.K., Teng, Y.H., Tan, J.J.M., Hsu, L.H.: Local diagnosis algorithms for multiprocessor systems under the comparison diagnosis model. IEEE Trans. Reliab. 62(4), 800\u2013810 (2013)","journal-title":"IEEE Trans. Reliab."},{"key":"210_CR39","doi-asserted-by":"crossref","unstructured":"Malek, M.: A comparison connection assignment for diagnosable of multiprocessor systems. In: Proceedings of the 7th International Symposium on Computer Architecture, pp. 31\u201336. (1980)","DOI":"10.1145\/800053.801906"},{"key":"210_CR40","unstructured":"Maeng, J., Malek, M.: A comparison connection assignment for self-diagnosis of multiprocessor systems. In: Proceeding 11th International Symposium on Fault Tolerant Computing, pp. 173\u2013175. (1981)"},{"issue":"6","key":"210_CR41","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1109\/PGEC.1967.264748","volume":"EC\u201316","author":"FP Preparata","year":"1967","unstructured":"Preparata, F.P., Metze, G., Chien, R.T.: On the connection assignment problem of diagnosable systems. IEEE Trans. Electron. Comput. EC\u201316(6), 848\u2013854 (1967)","journal-title":"IEEE Trans. Electron. Comput."},{"key":"210_CR42","doi-asserted-by":"crossref","first-page":"26","DOI":"10.2307\/2308012","volume":"62","author":"H Robbins","year":"1955","unstructured":"Robbins, H.: A remark of Stirling\u2019s formula. Am. Math. Mon. 62, 26\u201329 (1955)","journal-title":"Am. Math. Mon."},{"issue":"8","key":"210_CR43","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1109\/12.536232","volume":"45","author":"AK Somani","year":"1996","unstructured":"Somani, A.K., Peleg, O.: On diagnosability of large fault sets in regular topology-based computer systems. IEEE Trans. Comput. 45(8), 892\u2013902 (1996)","journal-title":"IEEE Trans. Comput."},{"key":"210_CR44","doi-asserted-by":"crossref","DOI":"10.5948\/UPO9781614440215","volume-title":"From Error-Correcting Codes Through Sphere Packings to Simple Groups","author":"TM Thompson","year":"1983","unstructured":"Thompson, T.M.: From Error-Correcting Codes Through Sphere Packings to Simple Groups. Mathematical Association of America, Washington, DC (1983)"},{"issue":"2","key":"210_CR45","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1109\/18.2632","volume":"34","author":"GJM Wee van","year":"1988","unstructured":"van Wee, G.J.M.: Improved sphere bounds on the covering radius of codes. IEEE Trans. Inf. Theory 34(2), 237\u2013245 (1988)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"9","key":"210_CR46","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1109\/12.312114","volume":"43","author":"D Wang","year":"1994","unstructured":"Wang, D.: Diagnosability of enhanced hypercubes. IEEE Trans. Comput. 43(9), 1054\u20131061 (1994)","journal-title":"IEEE Trans. Comput."},{"key":"210_CR47","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)","edition":"2"},{"issue":"2","key":"210_CR48","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1109\/12.364544","volume":"44","author":"J Xu","year":"1995","unstructured":"Xu, J., Huang, S.Z.: Sequentially $$t$$ t -diagnosable system: a characterization and its applications. IEEE Trans. Comput. 44(2), 340\u2013345 (1995)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"210_CR49","first-page":"208","volume":"E\u201310","author":"JM Xu","year":"2005","unstructured":"Xu, J.M., Zhu, Q., Hou, X.M., Zhou, T.: On restricted connectivity and extra connectivity of hypercubes and folded hypercubes. J. Shanghai Jiaotong Univ. (Sci.) E\u201310(2), 208\u2013212 (2005)","journal-title":"J. Shanghai Jiaotong Univ. (Sci.)"},{"issue":"4","key":"210_CR50","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1109\/TR.2013.2284743","volume":"62","author":"TL Ye","year":"2013","unstructured":"Ye, T.L., Hsieh, S.Y.: A scalable comparison-based diagnosis algorithm for hypercube-like networks. IEEE Trans. Reliab. 62(4), 789\u2013799 (2013)","journal-title":"IEEE Trans. Reliab."},{"issue":"3","key":"210_CR51","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/j.dam.2004.08.008","volume":"146","author":"T Yamada","year":"2005","unstructured":"Yamada, T., Ohtsukab, T., Watanabe, A., Ueno, S.: On sequential diagnosis of multiprocessor systems. Discrete Appl. Math. 146(3), 311\u2013342 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"210_CR52","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1109\/TR.2004.837528","volume":"53","author":"J Zhao","year":"2004","unstructured":"Zhao, J., Meyer, F.J., Park, N., Lombardi, F.: Sequential diagnosis of processor array systems. IEEE Trans. Reliab. 53(4), 487\u2013498 (2004)","journal-title":"IEEE Trans. Reliab."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0210-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0210-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0210-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,26]],"date-time":"2020-09-26T01:49:33Z","timestamp":1601084973000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0210-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,15]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["210"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0210-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,15]]}}}