Computing the (t,k)-diagnosability of component-composition graphs and its application

Sun Yuan Hsieh, Chun An Chen

研究成果: Conference contribution

4 引文 斯高帕斯(Scopus)

摘要

(t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors should be identified and repaired in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(G) and n(G) be the node connectivity and the number of nodes in G, respectively. We show that the class of m-dimensional component-composition graphs G for m ≥ 4 is (Ω(h),κ(G))-diagnosable, where h = 2 m-2 x lg (m-1)/m-1 if 2m-1 ≤ n(G) < m!; and h = 2m-2 if n(G) ≥ m!. Based on this result, the (t,k)-diagnosability of numerous multiprocessor systems can be computed efficiently.

原文English
主出版物標題Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
頁面363-374
頁數12
版本PART 2
DOIs
出版狀態Published - 2010 十二月 1
事件21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of
持續時間: 2010 十二月 152010 十二月 17

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
號碼PART 2
6507 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Other

Other21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
國家Korea, Republic of
城市Jeju Island
期間10-12-1510-12-17

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

指紋 深入研究「Computing the (t,k)-diagnosability of component-composition graphs and its application」主題。共同形成了獨特的指紋。

引用此