| Star图互连网络的容错性分析 |
| |
| 引用本文： | 聂晓冬,刘红美,徐俊明.Star图互连网络的容错性分析[J].数学物理学报(A辑),2004,24(2):168-176. |
| |
| 作者姓名： | 聂晓冬 刘红美 徐俊明 |
| |
| 作者单位： | [1]中国科学技术大学数学系，合肥230026 [2]三峡大学理学院，宜昌443002 |
| |
| 基金项目： | 国家自然科学基金项目 ( 1 0 3 0 1 0 3 1及 1 0 2 71 1 1 4)资助 |
| |
| 摘 要： | 限制连通度和限制容错直径是衡量互连网络可靠性的两个重要参数。当考察这两个参数时，总假设网络中和一台计算机相连接的所有计算机不会同时出现故障。该文证明了Star图互连网络的极小分离集和极小限制分离集的唯一性，然后得到了Star图的限制连通度是2n-4，当n=3,5和n≥7时，它的限制容错直径是|_3(n-1)/2_|+2，对于n =4, 6，限制容错直径是|_3(n-1)/2_|+3，即限制容错直径只比它的容错直径大1。
|
| 关 键 词： | Star图 连通度 容错性 限制连通度 限制容错直径 分离集 |
| 文章编号： | 1003-3998(2004)02-168-09 |
| 修稿时间： | 2001年12月24 |
The Fault Tolerant Analysis of Star Graph Interconnection Network |
| |
| NIE Xiao-Dong,LIU Hong-Mei,XU Jun-Ming.The Fault Tolerant Analysis of Star Graph Interconnection Network[J].Acta Mathematica Scientia,2004,24(2):168-176. |
| |
| Authors: | NIE Xiao-Dong LIU Hong-Mei XU Jun-Ming |
| |
| Abstract: | The restricted connectivity and the restricted fault diam eter are two reliability measures for interconnection networks, in which the aut hors assume that all the neighbors of a vertex do not fail at the same time. In this paper, the authors show the uniqueness of minimal (vertex) separating set s and of minimal restricted separating sets in the star graphs. The authors present that for the n star graph S_n, its restricted connectivity is 2n -4 and its restricted fault diameter is |_3(n-1)/2_|+2 and n≥7 and |_3(n-1)/2_|+3 for n=4,6, i.e., its fault diameter plus one. |
| |
| Keywords: | Star graph Connectivity Fault tolerance Restricted connectivity Restricted fault diameter Separating set |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《数学物理学报(A辑)》浏览原始摘要信息 |
| 点击此处可从《数学物理学报(A辑)》下载免费的PDF全文 |
