Conditional (t, k)-Diagnosis under the PMC Model

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

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

Title:	Conditional (t, k)-Diagnosis under the PMC Model
Authors:	Chang,GY
Contributors:	資訊工程學系
Keywords:	MULTIPROCESSOR SYSTEMS;DIAGNOSABLE SYSTEMS;NETWORKS
Date:	2011
Issue Date:	2012-03-27 18:57:44 (UTC+8)
Publisher:	國立中央大學
Abstract:	In this paper, assuming that each vertex is neighboring to at least one fault-free vertex, we investigate the (t, k)-diagnosability of a graph G under the PMC model. Lower bounds on the numeric degrees of (t, k)-diagnosability are suggested when G is a general graph or G is a regular graph. In particular, the following results are obtained. Symmetric d-dimensional grids are (N-m/2d, min{m, 2d - 1})-diagnosable, where d >= 2, 1 <= m <= 2d - 1, and N are the number of vertices. Symmetric d-dimensional tori are (N+0.62N(2/3)-2/4, 1)-diagnosable if d = 2, and (N-m/2d, min{m, 4d - 2})-diagnosable if d >= 3, where 1 <= m <= 4d - 2. Hypercubes are (N-2logN+2/logN, 2logN - 2)-iagnosable. Cube-connected cycles are (N-m/3, min{m, 4})-diagnosable, where 1 <= m <= 4; k-ary trees are (N-1/k, 1)-diagnosable.
Relation:	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Appears in Collections:	[Department of Computer Science and information Engineering] journal & Dissertation

Files in This Item:

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

社群 sharing