Strong Rabin numbers of folded hypercubes
The strong Rabin number of a network W of connectivity k is the minimum 1 so that for any k + 1 nodes s, d(1), d(2),..., d(k) of W, there exist k node-disjoint paths from s to d(1), d(2),.., d(k), respectively, whose maximal length is not greater than l, where s is not an element of {d(1), d(2),..., d(k)} and dl, d2,..., dk are not necessarily distinct. In this paper, we show that the strong Rabin number of a k-dimensional folded hypercube is [k/2] + 1, where [k/2] is the diameter of the k-dimensional folded hypercube. Each node-disjoint path we obtain has length not greater than the distance between the two end nodes plus two. This paper solves an open problem raised by Liaw and Chang. (c) 2005 Elsevier B.V. All rights reserved.
strong rabin number folded hypercube hypercube node-disjoint paths optimization problem