摘要
可诊断度是衡量一个互连网络可靠性的重要指标,常用来评估当系统中某些节点出现故障时将故障节点准确找出来的能力。PMC模型是一种经典的可诊断模型,被广泛地应用于系统诊断中,到目前为止,已经有很多的研究者基于PMC模型作出了大量研究成果。在PMC模型的基础上,对于不存在K_3子图的网络条件可诊断性进行了研究,并证明了当δ(G)≥9且任两个节点的共同邻居数不大于2时,无K_3子图的图G是2δ(G)-1条件可诊断的;当δ(G)≥6且任两个节点的共同邻居数不大于2时,二部图G是2δ(G)-1条件可诊断的。
The diagnosability is an important standard to judge the reliability of the interconnection network, in order to evaluate the capacity of a system to find the fauit nodes. The PMC model is a classical diagnostic model which has applied to sys- tem diagnosis widely. There are many researches under the PMC model have been proposed. This paper studied the conditional diagnosability of K3-free graphs under the PMC model. And it proved that when the number of eommom neighbors of any 2 nodes is not more than 2 with 8(G) 1〉9, then the conditional diagnosability of K3-free graph is 28(G) - 1. The paper also proves that when the number of commom neighbors of any 2 nodes is not more than 2 with 8(G) ≥6, the conditional diagnos- ability of bipartite graph is 28(G) - 1.
出处
《计算机应用研究》
CSCD
北大核心
2017年第8期2380-2382,2388,共4页
Application Research of Computers
基金
国家自然科学基金资助项目(61572340)
江苏省"六大人才高峰"项目(2014-WLW-010)
苏州市融合通信重点实验室(SKLCC2013XX)