期刊
COMPUTER JOURNAL
卷 59, 期 12, 页码 1839-1856出版社
OXFORD UNIV PRESS
DOI: 10.1093/comjnl/bxw037
关键词
interconnection network; graph; connectivity; diagnosability; PMC model; MM* model; bubble-sort star graph
类别
资金
- National Science Foundation of China [61370001, U1304601]
Connectivity plays an important role in measuring the fault tolerance of interconnection networks G = (V, E). A faulty set F subset of V is called a g-extra faulty set if every component of G-F has more than g nodes. A g-extra cut of G is a g-extra faulty set F such that G-F is disconnected. The minimum cardinality of g-extra cuts is said to be the g-extra connectivity of G. Diagnosability is an important metric for measuring the reliability of G. A new measure for fault diagnosis of G restrains that every fault-free component has at least (g + 1) fault-free nodes, which is called the g-extra diagnosability of G. As a favorable topology structure of interconnection networks, the n-dimensional bubble-sort star graph BSn has many good properties. In this paper, we prove that 2-extra connectivity of BSn is 6n - 15 for n >= 5 and the 2-extra connectivity of BS4 is 8; the 2-extra diagnosability of BSn is 6n - 13 under the PMC model for n >= 5 and the 2-extra diagnosability of BSn is 6n - 13 under the MM* model for n >= 6.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据