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

Sun Yuan Hsieh; Chun An Chen

doi:10.1007/978-3-642-17514-5_31

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 2^m-1 ≤ n(G) < m!; and h = 2^m-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	https://doi.org/10.1007/978-3-642-17514-5_31
出版狀態	Published - 2010 十二月 1
事件	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of 持續時間: 2010 十二月 15 → 2010 十二月 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

Other	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
國家	Korea, Republic of
城市	Jeju Island
期間	10-12-15 → 10-12-17

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

存取文件

10.1007/978-3-642-17514-5_31

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

引用此

Hsieh, S. Y., & Chen, C. A. (2010). Computing the (t,k)-diagnosability of component-composition graphs and its application. 於 Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings (PART 2 編輯, 頁 363-374). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 6507 LNCS, 編號 PART 2). https://doi.org/10.1007/978-3-642-17514-5_31

Hsieh, Sun Yuan ; Chen, Chun An. / Computing the (t,k)-diagnosability of component-composition graphs and its application. Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. 編輯 2010. 頁 363-374 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{9e1ba22380014ee7af2e7cafc8a12286,

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

abstract = "(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.",

author = "Hsieh, {Sun Yuan} and Chen, {Chun An}",

year = "2010",

month = dec,

day = "1",

doi = "10.1007/978-3-642-17514-5_31",

language = "English",

isbn = "3642175163",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 2",

pages = "363--374",

booktitle = "Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings",

edition = "PART 2",

note = "21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",

}

Hsieh, SY & Chen, CA 2010, Computing the (t,k)-diagnosability of component-composition graphs and its application. 於 Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 編號 PART 2, 卷 6507 LNCS, 頁 363-374, 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010, Jeju Island, Korea, Republic of, 10-12-15. https://doi.org/10.1007/978-3-642-17514-5_31

Computing the (t,k)-diagnosability of component-composition graphs and its application. / Hsieh, Sun Yuan; Chen, Chun An.

Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. 編輯 2010. p. 363-374 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 6507 LNCS, 編號 PART 2).

研究成果: Conference contribution

TY - GEN

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

AU - Hsieh, Sun Yuan

AU - Chen, Chun An

PY - 2010/12/1

Y1 - 2010/12/1

N2 - (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.

AB - (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.

UR - http://www.scopus.com/inward/record.url?scp=78650855442&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650855442&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17514-5_31

DO - 10.1007/978-3-642-17514-5_31

M3 - Conference contribution

AN - SCOPUS:78650855442

SN - 3642175163

SN - 9783642175169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 363

EP - 374

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -

Hsieh SY, Chen CA. Computing the (t,k)-diagnosability of component-composition graphs and its application. 於 Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 編輯 2010. p. 363-374. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). https://doi.org/10.1007/978-3-642-17514-5_31