Efficient unicast in bijective connection networks with the restricted faulty node set

详细信息    查看全文

• 作者：Jianxi Fan^a ; ^{jxfan@suda.edu.cn} ; Xiaohua Jia^b ; ^{csjia@cityu.edu.hk} ; Xin Liu^c ; ^{liuxin_star@163.com} ; Shukui Zhang^a ; ^{zhangsk@suda.edu.cn} ; Jia Yu^d ; ^{yujia@qdu.edu.cn}
• 关键词：Connectivity ; Set of restricted faulty nodes ; Unicast ; Fault-free path ; Bijective connection network
• 刊名：Information Sciences
• 出版年：2011
• 出版时间：1 June 2011
• 年：2011
• 卷：181
• 期：11
• 页码：2303-2315
• 全文大小：515 K

文摘

The connectivity is an important criteria to measure the fault-tolerant performance of a graph. However, the connectivity based on the condition of the set of arbitrary faulty nodes is generally lower. In this paper, in order to heighten this measure, we introduce the restricted connectivity into bijective connection networks. First, we prove that the probability that all the neighbors of an arbitrary node becomes faulty in any n-dimensional bijective connection network X_n is very low when n becomes sufficient large. Then, we give a constructive proof that under the condition that each node of an n-dimensional bijective connection network X_n has at least one fault-free neighbor, its restricted connectivity is 2n − 2, about half of the connectivity of X_n. Finally, by our constructive proof, we give an O(n) algorithm to get a reliable path of length at most n + 3log₂F + 1 between any two fault-free nodes in an n-dimensional bijective connection network. In particular, since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., our algorithm is appropriate for these cubes.