您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

J4 ›› 2013, Vol. 48 ›› Issue (7): 85-92.

• 前沿进展 • 上一篇    下一篇

分层立方网络的t/t-诊断度和诊断算法

LIN Li-mei1,2, ZHOU Shu-ming1,2, XU Li1,2   

  1. 1.福建师范大学数学与计算机科学学院, 福建 福州 350007;
    2.网络安全与密码技术福建省重点实验室, 福建 福州 350007
  • 收稿日期:2013-06-17 发布日期:2013-12-03
  • 作者简介:林丽美(1988- ),女,博士研究生, 研究方向为现代图论与网络优化. Email:putianlinlimei@163.com
  • 基金资助:

    国家自然科学基金资助项目(61072080);福建省教育厅A类项目(JA12073);福建省自然基金资助项目( 2013J01221, 2013J01222)

t/t-diagnosability and diagnosis algorithm on hierarchical cubic network

  1. 1. School of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350007, Fujian, China;
    2. Key Laboratory of Network Security and Cryptology, Fujian Normal University, Fuzhou 350007, Fujian, China
  • Received:2013-06-17 Published:2013-12-03

摘要:

故障诊断度在衡量一个多处理机系统的可靠性上起着极其重要的作用。悲观诊断策略(也称作t/t-诊断策略)在允许最多一个处理机误诊的情况下,能极大地提高多处理机系统的自我诊断度。本文主要证明了在 PMC诊断模型下,分层立方网络HCNn是(2n)/(2n)-可诊断的,同时,也给出了时间复杂度比原有的诊断算法较优的t/t诊断算法。

关键词: 分层立方网络; t/t-诊断度;PMC诊断模型

Abstract:

Fault diagnosability plays an extremely important role on measuring the reliability of a multiprocessor systems. Pessimistic diagnosis strategy, also known as t/t-diagnosis strategy, can greatly improve the multiprocessor system′s self diagnosability even under the condition that it allows a fault-free processor to be misdiagnosed. This paper mainly proves that hierarchical cubic network HCNn is (2n)/(2n) diagnosable under the PMC diagnosis model. At the same time, it also presents an optimal t/t-diagnosis algorithm on time complexity than the original diagnosis algorithm.

Key words: hierarchical cubic network; t/t-diagnosability; PMC diagnosis model

中图分类号: 

  • O157.5
[1] 朱恩强1,王治文2,张忠辅1. 若干倍图的Smarandachely邻点边染色[J]. J4, 2009, 44(12): 25-29.
[2] 董爱君 李国君 邹青松. 含相邻三角形的平面图的列表边和列表全染色[J]. J4, 2009, 44(10): 17-20.
[3] 王超. 图有哈密顿(g,f)-因子的度条件[J]. J4, 2009, 44(10): 21-25.
[4] 刘信生 朱志强. 图的点可区别IE-全色数的一个上界[J]. J4, 2009, 44(10): 14-16.
[5] 邹青松 李硕 杨兴刚. 二部图中包含六圈的度条件[J]. J4, 2009, 44(8): 13-15.
[6] 高玉芬 魏晓丽. 具有给定悬挂点数目的树的Merrifield-Simmons指标极值[J]. J4, 2009, 44(8): 16-20.
[7] 袁秀华. 图的符号边全控制数[J]. J4, 2009, 44(8): 21-24.
[8] 刘海英 马成刚 王志平. 刺图乘积上的Graham猜想[J]. J4, 2009, 44(8): 25-30.
[9] 段滋明 吕萍丽 苗连英 苗正科. 简单图的L(2,1,1)-标号[J]. J4, 2009, 44(8): 31-34.
[10] 刘晓妍. [s,t]-图泛圈性的一个充分条件[J]. J4, 2008, 43(12): 28-30.
[11] 耿建艳,颜 谨,李 峰 . 二部图中含指定顶点的独立4-圈[J]. J4, 2008, 43(5): 87-92 .
[12] 潘瑞霞,兰 梅,刘桂真 . 图存在分数[a,b]-因子的一个孤立韧度条件[J]. J4, 2008, 43(5): 93-96 .
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!