The g-Good-Neighbor conditional diagnosability of arrangement graphs

Limei Lin, Li Xu, Dajin Wang, Shuming Zhou

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

A network's diagnosability is the maximum number of faulty vertices the network can discriminate solely by performing mutual tests among the vertices. It is an important measure of a network's robustness. The original diagnosability without any condition is often rather low because it is bounded by the network's minimum degree. Several conditional diagnosability have been proposed in the past to increase the allowed faulty vertices, and hence enhancing the diagnosability of the network. The g-good-neighbor conditional diagnosability is the maximum number of faulty vertices a network can guarantee to identify, under the condition that every fault-free vertex has at least g fault-free neighbors (i.e., good neighbors). In this paper, we establish the g-good-neighbor conditional diagnosability for the (n,k)-arrangement graph network A{n,k}. We will show that, under both the PMC model and the comparison model, the A{n,k} 's g-good-neighbor conditional diagnosability is [(g+1)k-g](n-k) , which can be several times higher than the A{n,k} 's original diagnosability.

Original languageEnglish
Pages (from-to)542-548
Number of pages7
JournalIEEE Transactions on Dependable and Secure Computing
Volume15
Issue number3
DOIs
StatePublished - 1 May 2018

Keywords

  • -good-neighbor conditional diagnosability
  • Arrangement graph networks
  • PMC model
  • comparison model
  • system-level diagnosis

Cite this

@article{ddc3ed17e3744a43b3520d992b06d9b8,
title = "The g-Good-Neighbor conditional diagnosability of arrangement graphs",
abstract = "A network's diagnosability is the maximum number of faulty vertices the network can discriminate solely by performing mutual tests among the vertices. It is an important measure of a network's robustness. The original diagnosability without any condition is often rather low because it is bounded by the network's minimum degree. Several conditional diagnosability have been proposed in the past to increase the allowed faulty vertices, and hence enhancing the diagnosability of the network. The g-good-neighbor conditional diagnosability is the maximum number of faulty vertices a network can guarantee to identify, under the condition that every fault-free vertex has at least g fault-free neighbors (i.e., good neighbors). In this paper, we establish the g-good-neighbor conditional diagnosability for the (n,k)-arrangement graph network A{n,k}. We will show that, under both the PMC model and the comparison model, the A{n,k} 's g-good-neighbor conditional diagnosability is [(g+1)k-g](n-k) , which can be several times higher than the A{n,k} 's original diagnosability.",
keywords = "-good-neighbor conditional diagnosability, Arrangement graph networks, PMC model, comparison model, system-level diagnosis",
author = "Limei Lin and Li Xu and Dajin Wang and Shuming Zhou",
year = "2018",
month = "5",
day = "1",
doi = "10.1109/TDSC.2016.2593446",
language = "English",
volume = "15",
pages = "542--548",
journal = "IEEE Transactions on Dependable and Secure Computing",
issn = "1545-5971",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "3",

}

The g-Good-Neighbor conditional diagnosability of arrangement graphs. / Lin, Limei; Xu, Li; Wang, Dajin; Zhou, Shuming.

In: IEEE Transactions on Dependable and Secure Computing, Vol. 15, No. 3, 01.05.2018, p. 542-548.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The g-Good-Neighbor conditional diagnosability of arrangement graphs

AU - Lin, Limei

AU - Xu, Li

AU - Wang, Dajin

AU - Zhou, Shuming

PY - 2018/5/1

Y1 - 2018/5/1

N2 - A network's diagnosability is the maximum number of faulty vertices the network can discriminate solely by performing mutual tests among the vertices. It is an important measure of a network's robustness. The original diagnosability without any condition is often rather low because it is bounded by the network's minimum degree. Several conditional diagnosability have been proposed in the past to increase the allowed faulty vertices, and hence enhancing the diagnosability of the network. The g-good-neighbor conditional diagnosability is the maximum number of faulty vertices a network can guarantee to identify, under the condition that every fault-free vertex has at least g fault-free neighbors (i.e., good neighbors). In this paper, we establish the g-good-neighbor conditional diagnosability for the (n,k)-arrangement graph network A{n,k}. We will show that, under both the PMC model and the comparison model, the A{n,k} 's g-good-neighbor conditional diagnosability is [(g+1)k-g](n-k) , which can be several times higher than the A{n,k} 's original diagnosability.

AB - A network's diagnosability is the maximum number of faulty vertices the network can discriminate solely by performing mutual tests among the vertices. It is an important measure of a network's robustness. The original diagnosability without any condition is often rather low because it is bounded by the network's minimum degree. Several conditional diagnosability have been proposed in the past to increase the allowed faulty vertices, and hence enhancing the diagnosability of the network. The g-good-neighbor conditional diagnosability is the maximum number of faulty vertices a network can guarantee to identify, under the condition that every fault-free vertex has at least g fault-free neighbors (i.e., good neighbors). In this paper, we establish the g-good-neighbor conditional diagnosability for the (n,k)-arrangement graph network A{n,k}. We will show that, under both the PMC model and the comparison model, the A{n,k} 's g-good-neighbor conditional diagnosability is [(g+1)k-g](n-k) , which can be several times higher than the A{n,k} 's original diagnosability.

KW - -good-neighbor conditional diagnosability

KW - Arrangement graph networks

KW - PMC model

KW - comparison model

KW - system-level diagnosis

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

U2 - 10.1109/TDSC.2016.2593446

DO - 10.1109/TDSC.2016.2593446

M3 - Article

AN - SCOPUS:85047191562

VL - 15

SP - 542

EP - 548

JO - IEEE Transactions on Dependable and Secure Computing

JF - IEEE Transactions on Dependable and Secure Computing

SN - 1545-5971

IS - 3

ER -