期刊
THEORETICAL COMPUTER SCIENCE
卷 898, 期 -, 页码 30-43出版社
ELSEVIER
DOI: 10.1016/j.tcs.2021.10.015
关键词
Interconnection networks; R-g-conditional connectivity; (n, k)-star graphs; (n, k)-bubble-sort graphs
资金
- National Natural Science Foundation of China [61402317]
- Shanxi Province Science Foundation [201901D111253]
- Scientific and Technological Innovation Team of Shanxi Province [201805D131007]
- Taiyuan University of Science and Technology Doctoral Fund [20202058]
This paper examines the relationship between the conditional diagnosability and connectivity of a multiprocessor system graph, exploring the calculations of diagnosability under different models and presenting the results under corresponding conditions.
The R-g-conditional diagnosability of a multiprocessor system modeled by a graph G, denoted by t(Rg)(G), is a generalization of conditional diagnosability, which restricts every vertex contains at least g fault-free neighbors. Particularly, the R-1-conditional diagnosability is the conditional diagnosability. The R-g-conditional connectivity of a graph G, denoted by kappa(Rg) (G), is the minimum number of vertices, whose deletion will disconnect the graph and every vertex of G has at least g neighbors in the remaining subgraphs. In this paper, the relationships between the R-g-conditional connectivity of a graph G and its R-g-conditional diagnosability under the PMC and MM* models are explored. We establish the Rg-conditional diagnosability t(Rg) (G) equals kappa(R2g+1) (G) + g under some reasonable conditions, except the R-1-conditional diagnosability of G under the MM* model. Moreover, we show under the MM* model, t(R1) (G) = kappa(R2)(G) with similar conditions. Applying our results, the R-g-conditional diagnosability of the (n, k)-star graphs and the (n, k)-bubble-sort graphs are determined. (C) 2021 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据