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(2)vertical bar F vertical bar] + 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, Mobius cubes, etc., our algorithm is appropriate for these cubes. (C) 2010 Elsevier Inc. All rights reserved.