《计算机应用研究》|Application Research of Computers

K3子图的互连网络在PMC模型下的条件可诊断度

Conditional diagnosability of K3-free graph under PMC model

免费全文下载 (已被下载 次)  
获取PDF全文
作者 曹骞,陈琪,张书奎,林政宽
机构 苏州大学 计算机科学与技术学院,江苏 苏州 215006
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2017)08-2380-03
DOI 10.3969/j.issn.1001-3695.2017.08.033
摘要 可诊断度是衡量一个互连网络可靠性的重要指标,常用来评估当系统中某些节点出现故障时将故障节点准确找出来的能力。PMC模型是一种经典的可诊断模型,被广泛地应用于系统诊断中,到目前为止,已经有很多的研究者基于PMC模型作出了大量研究成果。在PMC模型的基础上,对于不存在K3子图的网络条件可诊断性进行了研究,并证明了当δ(G)≥9且任两个节点的共同邻居数不大于2时,无K3子图的图G是2δ(G)-1条件可诊断的;当δ(G)≥6且任两个节点的共同邻居数不大于2时,二部图G是2δ(G)-1条件可诊断的。
关键词 条件可诊断性;无K3子图的图;PMC模型;互连网络
基金项目 国家自然科学基金资助项目(61572340)
江苏省“六大人才高峰”项目(2014-WLW-010)
苏州市融合通信重点实验室(SKLCC2013XX)
本文URL http://www.arocmag.com/article/01-2017-08-033.html
英文标题 Conditional diagnosability of K3-free graph under PMC model
作者英文名 Cao Qian, Chen Qi, Zhang Shukui, Lin Zhengkuan
机构英文名 SchoolofComputerScience&Technology,SoochowUniversity,SuzhouJiangsu215006,China
英文摘要 The diagnosability is an important standard to judge the reliability of the interconnection network, in order to eval-uate the capacity of a system to find the fault nodes. The PMC model is a classical diagnostic model which has applied to system diagnosis widely. There are many researches under the PMC model have been proposed. This paper studied the conditional diagnosability of K3-free graphs under the PMC model. And it proved that when the number of commom neighbors of any 2 nodes is not more than 2 with δ(G)≥9, then the conditional diagnosability of K3-free graph is 2δ(G)-1. The paper also proves that when the number of commom neighbors of any 2 nodes is not more than 2 with δ(G)≥6, the conditional diagnosability of bipartite graph is 2δ(G)-1.
英文关键词 conditional diagnosability; K3-free graph; PMC model; interconnection network
参考文献 查看稿件参考文献
  [1] Chang Naiwen, Hsieh S Y. Conditional diagnosability of augmented cubes under the PMC model[J] . IEEE Trans on Dependable Secure Computing, 2012, 9(1):46-60.
[2] Hsieh S Y, Chuang T Y. The strong diagnosability of regular networks and product networks under the PMC model[J] . IEEE Trans on Parallel and Distributed Systems, 2008, 20(3):367-378.
[3] Zhou Shuming, Wang Jian, Xu Xirong, et al. Conditional fault diagnosis of bubble sort graphs under the PMC model[J] . Intelligence Computation and Evolutionary Computation, 2013, 180:53-59.
[4] Tsai C H. A quick pessimistic diagnosis algorithm for hypercube-like multiprocessor systems under the PMC model[J] . IEEE Trans on Computers, 2013, 62(2):259-267.
[5] Preparata F P, Metz G, Chien R T. On the connection assignment problem of diagnosable systems[J] . IEEE Trans on Electronic Computers, 1967, 16(6):848-854.
[6] Chang G Y, Chen G H, Chang G J. (t, k)-diagnosis for matching composition networks under the MM* model[J] . IEEE Trans on Computers, 2006, 55(1):88-92.
[7] Yan Shaohua. Diagnosability of cross-cube under PMC diagnostic mo-del[J] . Computer Engineering and Applications, 2011, 47(17):83-86.
[8] Hakimi S L, Amin A T. Characterization of connection assignment of diagnosable systems[J] . IEEE Trans on Computers, 1974, 23(1):86-88.
[9] 李小燕, 杨小雪, 周书明. 扭立方连接网络的故障诊断分析[J] . 福建师范大学学报:自然科学版, 2013, 29(5):20-25.
[10] Ahlswede R, Aydinian H. On diagnosability of large multiprocessor networks[J] . Discrete Applied Mathematics, 2008, 156(18):3464-3474.
[11] 周俊. 互连网络的可诊断性及容错性[D] . 西安:西安电子科技大学, 2014.
[12] 闫少华, 樊建席. 基于PMC模型的高效人工免疫诊断算法[J] . 计算机应用与软件, 2012, 29(4):27-30.
[13] Lin Chengkuan, Teng Y H. The diagnosability of triangle-free graphs[J] . Theoretical Computer Science, 2014, 530:58-65.
[14] Hsu L H, Lin Chengkuan. Graph theory and interconnection networks[M] . [S. l. ] :CRC Press, 2008.
[15] Dahbura A T, Masson G M. Anfault identification algorithm for diagnosable systems[J] . IEEE Trans on Computers, 1984, 33(6):486-492.
收稿日期 2016/6/16
修回日期 2016/8/1
页码 2380-2382,2388
中图分类号 TP306
文献标志码 A