(t,k)-diagnosis for component-composition graphs under the MM* model

Chun An Chen, Sun-Yuan Hsieh

Research output: Contribution to journalArticle

29 Citations (Scopus)

Abstract

(t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least t faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(G) and n(G) be, respectively, the node connectivity and the number of nodes in a graph G. In this paper, we compute the (t, k)-diagnosability for a class of component composition graphs under the comparison diagnosis model. We show that the m-dimensional component-composition graph G (m ≥ 4) is (Ω(h),κ(G))-diagnosable, where h= 2m-1 × (m -3) × lg(m-1) (m-1)/(m-1) 2 if 2m-2 ≤ n(G)<; m 2m-1 × (m-3)/m-1 if n(G) ≥ m!. Based on this result, the (t, k)-diagnosability of several multiprocessor systems, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply twisted cubes, generalized twisted cubes, recursive circulants, Mobius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs, can be computed efficiently.

Original languageEnglish
Article number5601693
Pages (from-to)1704-1717
Number of pages14
JournalIEEE Transactions on Computers
Volume60
Issue number12
DOIs
Publication statusPublished - 2011 Dec 1

Fingerprint

Regular hexahedron
Graph in graph theory
Chemical analysis
Diagnosability
Stars
Bubble sort
Crossed Cube
Model
Star Graph
Möbius
Multiprocessor Systems
Vertex of a graph
Hypercube
Multiplication
Connectivity
Iteration

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

@article{e2a86ce13acb42e19e0cd758e004955d,
title = "(t,k)-diagnosis for component-composition graphs under the MM* model",
abstract = "(t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least t faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(G) and n(G) be, respectively, the node connectivity and the number of nodes in a graph G. In this paper, we compute the (t, k)-diagnosability for a class of component composition graphs under the comparison diagnosis model. We show that the m-dimensional component-composition graph G (m ≥ 4) is (Ω(h),κ(G))-diagnosable, where h= 2m-1 × (m -3) × lg(m-1) (m-1)/(m-1) 2 if 2m-2 ≤ n(G)<; m 2m-1 × (m-3)/m-1 if n(G) ≥ m!. Based on this result, the (t, k)-diagnosability of several multiprocessor systems, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply twisted cubes, generalized twisted cubes, recursive circulants, Mobius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs, can be computed efficiently.",
author = "Chen, {Chun An} and Sun-Yuan Hsieh",
year = "2011",
month = "12",
day = "1",
doi = "10.1109/TC.2010.201",
language = "English",
volume = "60",
pages = "1704--1717",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "12",

}

(t,k)-diagnosis for component-composition graphs under the MM* model. / Chen, Chun An; Hsieh, Sun-Yuan.

In: IEEE Transactions on Computers, Vol. 60, No. 12, 5601693, 01.12.2011, p. 1704-1717.

Research output: Contribution to journalArticle

TY - JOUR

T1 - (t,k)-diagnosis for component-composition graphs under the MM* model

AU - Chen, Chun An

AU - Hsieh, Sun-Yuan

PY - 2011/12/1

Y1 - 2011/12/1

N2 - (t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least t faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(G) and n(G) be, respectively, the node connectivity and the number of nodes in a graph G. In this paper, we compute the (t, k)-diagnosability for a class of component composition graphs under the comparison diagnosis model. We show that the m-dimensional component-composition graph G (m ≥ 4) is (Ω(h),κ(G))-diagnosable, where h= 2m-1 × (m -3) × lg(m-1) (m-1)/(m-1) 2 if 2m-2 ≤ n(G)<; m 2m-1 × (m-3)/m-1 if n(G) ≥ m!. Based on this result, the (t, k)-diagnosability of several multiprocessor systems, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply twisted cubes, generalized twisted cubes, recursive circulants, Mobius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs, can be computed efficiently.

AB - (t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least t faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(G) and n(G) be, respectively, the node connectivity and the number of nodes in a graph G. In this paper, we compute the (t, k)-diagnosability for a class of component composition graphs under the comparison diagnosis model. We show that the m-dimensional component-composition graph G (m ≥ 4) is (Ω(h),κ(G))-diagnosable, where h= 2m-1 × (m -3) × lg(m-1) (m-1)/(m-1) 2 if 2m-2 ≤ n(G)<; m 2m-1 × (m-3)/m-1 if n(G) ≥ m!. Based on this result, the (t, k)-diagnosability of several multiprocessor systems, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply twisted cubes, generalized twisted cubes, recursive circulants, Mobius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs, can be computed efficiently.

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

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

U2 - 10.1109/TC.2010.201

DO - 10.1109/TC.2010.201

M3 - Article

AN - SCOPUS:84873465914

VL - 60

SP - 1704

EP - 1717

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 12

M1 - 5601693

ER -