{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:52Z","timestamp":1759637692076,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,6,1]],"date-time":"2014-06-01T00:00:00Z","timestamp":1401580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001868","name":"National Science Council Taiwan","doi-asserted-by":"publisher","award":["NSC101-2221-E-006-236"],"award-info":[{"award-number":["NSC101-2221-E-006-236"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p>Diagnosability is an important metric for measuring the reliability of multiprocessor systems. This article adopts the MM* model and outlines the common properties of a wide class of interconnection networks, called component-composition graphs (CCGs), to determine their diagnosability by using their obtained properties. By applying the results to multiprocessor systems, the diagnosability of hypercube-like networks (including hypercubes, crossed cubes, M\u00f6bius cubes, twisted cubes, locally twisted cubes, generalized twisted cubes, and recursive circulants), star graphs, pancake graphs, bubble-sort graphs, and burnt pancake graphs, all of which belong to the class of CCGs, can also be computed.<\/jats:p>","DOI":"10.1145\/2611759","type":"journal-article","created":{"date-parts":[[2014,6,17]],"date-time":"2014-06-17T12:38:13Z","timestamp":1403008693000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Diagnosability of Component-Composition Graphs in the MM* Model"],"prefix":"10.1145","volume":"19","author":[{"given":"Chia-Wei","family":"Lee","sequence":"first","affiliation":[{"name":"National Cheng Kung University, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sun-Yuan","family":"Hsieh","sequence":"additional","affiliation":[{"name":"National Cheng Kung University, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,6,23]]},"reference":[{"volume-title":"Proceedings of the International Conference on Parallel Processing. 393--400","author":"Akers S. B.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.21148"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/47.1.85"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1214345"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675844"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1976.1674658"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676437"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2005.44"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00054-G"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2010.201"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675807"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.381950"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790187539"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.159036"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2002.1019858"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/25489.25499"},{"volume-title":"Proceedings of 21st International Symposium on Algorithms and Computation (ISAAC'10)","author":"Hsieh S. Y.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2008.30"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2008.104"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2008.99"},{"key":"e_1_2_1_23_1","first-page":"2588","article-title":"An algorithm for node-to-set disjoint paths problem in burnt pancake graphs. IEICE","volume":"12","author":"Kaneko K.","year":"2003","journal-title":"Trans. Inf. Syst. E86-D"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.50"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2010.22"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2009.52"},{"key":"e_1_2_1_27_1","unstructured":"C. W. Lee and S. Y. Hsieh. 2013. Diagnosabiltiy of multiprocessor systems. InScalable Computing and Communications: Theory and Practice. Wiley.  C. W. Lee and S. Y. Hsieh. 2013. Diagnosabiltiy of multiprocessor systems. InScalable Computing and Communications: Theory and Practice. Wiley."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.59861"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"F. T. Leighton. 1992. Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes. Morgan Kaufmann San Fransisco.   F. T. Leighton. 1992. Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes. Morgan Kaufmann San Fransisco.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"volume-title":"Proceedings of 11th International Symposium on Fault-Tolerant Computing. 173--175","author":"Maeng J.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00176-6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.029"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1967.264748"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.177309"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPDP.1993.395450"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.817401"},{"key":"e_1_2_1_37_1","first-page":"789","article-title":"The connectivity and super connectivity of bubble-sort graph","volume":"35","author":"Xu M.","year":"2012","journal-title":"Acta Mathematicae Sinica"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1080\/0020716042000301752"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.09.011"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2611759","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2611759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:33Z","timestamp":1750230093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2611759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.1145\/2611759"],"URL":"https:\/\/doi.org\/10.1145\/2611759","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2014,6]]},"assertion":[{"value":"2013-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}