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

摘要

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 + 3?log 2F? + 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.