{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:54:21Z","timestamp":1772121261840,"version":"3.50.1"},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2020,12,14]],"date-time":"2020-12-14T00:00:00Z","timestamp":1607904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Natural Science Foundation of Shanxi Provincial","award":["201801D221193"],"award-info":[{"award-number":["201801D221193"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61502330"],"award-info":[{"award-number":["61502330"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11671296"],"award-info":[{"award-number":["11671296"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11701407"],"award-info":[{"award-number":["11701407"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,5,17]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The diagnosability is one of the most important measures of the reliability of networks. Consider the setting where there are large-scale failures that disconnect the network and result in many components. Then, the diagnosability is closely related to the number of components. In this paper, we define and study the $\\boldsymbol{g}$-component diagnosability of network $\\boldsymbol{G}$, which is denoted by $\\boldsymbol{ct_g(G)}$ and has not been addressed before. $\\boldsymbol{ct_g(G)}$ is the maximum number of nodes in the faulty node set $\\boldsymbol{F}$ of $\\boldsymbol{G}$ such that $\\boldsymbol{G-F}$ has at least $\\boldsymbol{g}$ components and diagnosis model can identify all nodes in $\\boldsymbol{F}$. Under PMC and MM$^*$ diagnosis models, we show that, in the hypercube $\\boldsymbol{Q_n\\ (n\\geq 7)}$, $\\boldsymbol{ct_{g+1}(Q_n)=-(1\/2)g^2+(n-3\/2)g+n}$ when $\\boldsymbol{g\\leq n-1}$. Moreover, we determine the $\\boldsymbol{(n+1)}$-component diagnosability $\\boldsymbol{ct_{n+1}(Q_n)=n^2\/2+n\/2-2}$ for $\\boldsymbol{n\\geq 7}$.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaa155","type":"journal-article","created":{"date-parts":[[2020,11,26]],"date-time":"2020-11-26T04:11:09Z","timestamp":1606363869000},"page":"1129-1143","source":"Crossref","is-referenced-by-count":34,"title":["The Component Diagnosability of Hypercubes with Large-Scale Faulty Nodes"],"prefix":"10.1093","volume":"65","author":[{"given":"Shurong","family":"Zhang","sequence":"first","affiliation":[{"name":"College of Mathematics, Taiyuan University of Technology, Taiyuan, Shanxi 030024, P.R. China"}]},{"given":"Dongyue","family":"Liang","sequence":"additional","affiliation":[{"name":"College of Mathematics, Taiyuan University of Technology, Taiyuan, Shanxi 030024, P.R. China"}]},{"given":"Lin","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Data and Computer Science, Sun Yat-Sen University, Guangzhou, Guangdong 510275, P.R. China"}]},{"given":"Ronghua","family":"Li","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, P.R. China"}]},{"given":"Weihua","family":"Yang","sequence":"additional","affiliation":[{"name":"College of Mathematics, Taiyuan University of Technology, Taiyuan, Shanxi 030024, P.R. China"}]}],"member":"286","published-online":{"date-parts":[[2020,12,14]]},"reference":[{"key":"2022051812594985400_ref1","volume-title":"Graph Theory","author":"Bondy","year":"2007"},{"key":"2022051812594985400_ref2","first-page":"1622","article-title":"Conditional $\\left (t,k\\right )$-diagnosis in graphs by using the comparison diagnosis model","volume":"64","author":"Chun-An","year":"2015","journal-title":"IEEE Trans. Comput."},{"key":"2022051812594985400_ref3","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1109\/TC.2012.58","article-title":"Component-composition graphs: $\\left (t,k\\right )$-Diagnosability and its application","volume":"62","author":"Chun-An","year":"2013","journal-title":"IEEE Trans. Comput."},{"key":"2022051812594985400_ref4","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1109\/TC.1984.1676472","article-title":"An O(${n}^{2.5}$) faulty identification algorithm for diagnosable systems","volume":"C-33","author":"Anton","year":"1984","journal-title":"IEEE Trans. Comput."},{"key":"2022051812594985400_ref5","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1080\/00207160.2011.638978","article-title":"Component connectivity of the hypercubes","volume":"89","author":"Lih-Hsing","year":"2012","journal-title":"Int. J. Comput. Math."},{"key":"2022051812594985400_ref6","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.tcs.2018.09.014","article-title":"The extra connectivity, extra conditional diagnosability and $t\/k$-diagnosability of the data center network DCell","volume":"766","author":"Xiaoyan","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"2022051812594985400_ref7","first-page":"1","article-title":"Diagnosability evaluation of the data center network DCell","volume":"61","author":"Xiaoyan","year":"2018","journal-title":"Comput. J."},{"key":"2022051812594985400_ref8","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.tcs.2019.12.001","article-title":"The extra connectivity and extra diagnosability of regular interconnection networks","volume":"809","author":"Mengjie","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"2022051812594985400_ref9","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/TC.2005.19","article-title":"Conditional diagnosability measures for large multiprocessor systems","volume":"54","author":"Pao-Lien","year":"2005","journal-title":"IEEE Trans. Comput."},{"key":"2022051812594985400_ref10","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1109\/TPDS.2015.2400459","article-title":"The extra, restricted connectivity and conditional diagnosability of split-star networks","volume":"27","author":"Limei","year":"2016","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2022051812594985400_ref11","doi-asserted-by":"crossref","first-page":"3157","DOI":"10.1109\/TC.2015.2512866","article-title":"Diagnosability for regular networks","volume":"65","author":"Limei","year":"2016","journal-title":"IEEE Trans. Comput."},{"key":"2022051812594985400_ref12","doi-asserted-by":"crossref","first-page":"2352","DOI":"10.1109\/TPDS.2014.2347961","article-title":"The extra connectivity and conditional diagnosability of alternating group networks","volume":"26","author":"Limei","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2022051812594985400_ref13","first-page":"173","article-title":"A Comparison Connection Assignment for Self-diagnosis of Multiprocessor Systems","volume-title":"Proc. 11th Int. Symposium on Fault-Tolerant Computing","author":"Maeng","year":"1981"},{"key":"2022051812594985400_ref14","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1109\/PGEC.1967.264748","article-title":"On the connection assignment problem of diagnosable systems","volume":"EC-16","author":"Franco","year":"1967","journal-title":"IEEE Trans. Electron. Comput."},{"key":"2022051812594985400_ref15","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1109\/12.177309","article-title":"On self-diagnosable multiprocessor system: Diagnosis by the comparison approach","volume":"41","author":"Abhijit","year":"1992","journal-title":"IEEE Trans. Comput."},{"key":"2022051812594985400_ref16","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1109\/12.536232","article-title":"On diagnosability of large fault sets in regular topology-based computer systems","volume":"45","author":"Arun","year":"1996","journal-title":"IEEE Trans. Comput."},{"key":"2022051812594985400_ref17","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1109\/TPDS.2014.2387284","article-title":"Optimal edge congestion of exchanged hypercubes","volume":"27","author":"Tsung-Han","year":"2016","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2022051812594985400_ref18","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.ipl.2005.10.003","article-title":"Minimum neighborhood in a generalized cube","volume":"97","author":"Xiaofan","year":"2006","journal-title":"Inf. Process. Lett."},{"key":"2022051812594985400_ref19","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1080\/00207160410001661726","article-title":"On the maximal connected component of hypercube with faulty vertices","volume":"81","author":"Xiaofan","year":"2004","journal-title":"Int. J. Comput. Math."},{"key":"2022051812594985400_ref20","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1080\/00207160500113173","article-title":"On the maximal connected component of a hypercube with faulty vertices III","volume":"83","author":"Xiaofan","year":"2006","journal-title":"Int. J. Comput. Math."},{"key":"2022051812594985400_ref21","doi-asserted-by":"crossref","first-page":"2884","DOI":"10.1109\/TC.2015.2506562","article-title":"A fast pessimistic diagnosis algorithm for hypercube-like networks under the comparison model","volume":"65","author":"Liang-Cheng","year":"2016","journal-title":"IEEE Trans. Comput."},{"key":"2022051812594985400_ref22","doi-asserted-by":"crossref","first-page":"1165","DOI":"10.1109\/TPDS.2014.2318305","article-title":"The $g$ good-neighbor conditional diagnosability of $k$-ary $n$-cubes under the PMC model and MM$^{\\ast } $ model","volume":"26","author":"Jun","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2022051812594985400_ref23","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0890-5401(87)90011-3","article-title":"An efficient algorithm for multiprocessor fault diagnosis using the comparison approach","volume":"74","author":"Che-Liang","year":"1987","journal-title":"Inf. Comput."},{"key":"2022051812594985400_ref24","doi-asserted-by":"crossref","first-page":"1046","DOI":"10.1109\/TPDS.2016.2609428","article-title":"ExCCC-DCN: A highly scalable, cost-effective and energy-efficient data center structure","volume":"28","author":"Zhen","year":"2017","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2022051812594985400_ref25","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1109\/TPDS.2018.2874659","article-title":"HSDC: A highly scalable data center network architecture for greater incremental scalability","volume":"30","author":"Zhen","year":"2019","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2022051812594985400_ref26","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1109\/TC.2013.228","article-title":"The $t\/k$-Diagnosability of star graph networks","volume":"64","author":"Shuming","year":"2015","journal-title":"IEEE Trans. Comput."},{"key":"2022051812594985400_ref27","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2016.05.035","article-title":"Component connectivity of hypercubes","volume":"640","author":"Shuli","year":"2016","journal-title":"Theor. Comput. Sci."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/5\/1129\/43731820\/bxaa155.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/5\/1129\/43731820\/bxaa155.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T13:01:50Z","timestamp":1652878910000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/65\/5\/1129\/6032262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,14]]},"references-count":27,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2020,12,14]]},"published-print":{"date-parts":[[2022,5,17]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaa155","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,5]]},"published":{"date-parts":[[2020,12,14]]}}}