文献类型：期刊文章

作　　者：刘长河[1,2,3] 童明生[1,2,3] 范天佑[1,2,3]

机构地区：[1]北京建工学院基础部 [2]北京理工大学材料中心 [3]北京理工大学计算中心

出　　处：《计算机学报》

基　　金：北京建工学院青年科研基金

年　　份：1999

卷　　号：22

期　　号：2

起止页码：120-125

语　　种：中文

收录情况：BDHX、BDHX1996、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：超立方是分布存储系中最常用的结构．在以往的工作中，人们已经提出了不少容错寻径算法．然而，还没有考虑Ｈｎ中｜Ｆ｜２ｎ－２的情形．在一个含有故障结点集Ｆ的ｎ维超立方网络Ｈｎ中，｜Ｆ｜４ｎ－２４，（ｓ０，ｄ０），（ｓ１，ｄ１）是其中任意两对非故障结点，如果，（１）对于ｖ∈Ｖ（Ｈｎ），有｜Ａ（ｖ，Ｈｎ－Ｆ）｜６．（２）沿着某一维ｋ（０ｋｎ－１），可将Ｈｎ分割成两部分：（ｄ０∈）Ｈｎ－１，０和（ｄ１∈）Ｈｎ－１，１，且｜Ｆ∩Ｈｎ－１，ｉ｜２ｎ－１２（ｉ＝０，１），则一定存在两条互不相交的路径Ｐ（ｓｉ，ｄｉ），使得｜Ｐ（ｓｉ，ｄｉ）｜Ｈ（ｓｉ，ｄｉ）＋１２（ｉ＝０，１）．并且，这两条路径可以并行地求得．我们给出了相应的容错寻径算法，其时间复杂性为ｔ＝Ｏ（ｎ·｜Ｆ｜）．

关 键 词：图论 互连网络 寻径算法 超立方网络

分 类 号：O157.5[数学类] TP301.6]