Conditional (t,k)-Diagnosis in graphs by using the comparison diagnosis model

NCUIR > College of Electrical Engineering & Computer Science > Department of Computer Science and information Engineering > journal & Dissertation > Item 987654321/106506

Please use this identifier to cite or link to this item: https://ir.lib.ncu.edu.tw/handle/987654321/106506

Title:	Conditional (t,k)-Diagnosis in graphs by using the comparison diagnosis model
Authors:	張貴雲;Chen, Chun-An;Chang, Guey-Yun;Hsieh, Sun-Yuan
Contributors:	資訊電機學院資訊工程學系
Keywords:	Circuit faults;Computational modeling;Computer simulation;Diagnosis;Educational institutions;Fault diagnosis;Graphs;Lower bounds;Multiprocessing systems;Processors;Program processors;Sequential diagnosis;Symmetry;Toruses;Transaction processing
Date:	2015-06-01
Issue Date:	2026-04-23 13:25:36 (UTC+8)
Publisher:	IEEE Computer Society;New York: IEEE
Abstract:	摘要： (t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors be identified and repaired in each iteration when there are at most t faulty processors, where t ≥ k. Based on the assumption that each vertex is adjacent to at least one fault-free vertex, the conditional (t, k)-diagnosis of graphs was investigated by using the comparison diagnosis model. Lower bounds on the conditional (t, k)-diagnosability of graphs were derived, and applied to obtain the following results. 1) Symmetric d-dimensional grids are conditionally (N/2d+1 -1, 2d -1)-diagnosable when d ≥ 2 and N (the number of vertices) ≥ 4 d . 2) Symmetric d-dimensional tori are conditionally (1/5 (N + min{8/5 N 2/3 , 2N-20/15} - 2), 6)-diagnosable when d = 2 and N ≥ 49 and ( N/2d+1 -1, 4d-2)-diagnosable when d ≥ 3 and N ≤ 4 d . 3) Cube-connected cycles are conditionally (N/4 - 1, 4)-diagnosable. 4) k-ary trees are conditionally (N/k+1 - 1)-diagnosable. 其他題名： TC 出版者： New York: IEEE 出版日期： 2015-06-01 出處： IEEE transactions on computers, 2015-06, Vol.64 (6), p.1622-1632 資源來源： IEEE Xplore Digital Library (LUT) 版權： Copyright The Institute of Electrical and Electronics Engineers, Inc. (IEEE) Jun 2015 識別號： ISSN: 0018-9340 識別號： EISSN: 1557-9956 識別號： DOI: 10.1109/TC.2014.2345407 識別號： CODEN: ITCOB4
Appears in Collections:	[Department of Computer Science and information Engineering] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	14	View/Open

社群 sharing

Loading...