Article ID Journal Published Year Pages File Type
9657801 Theoretical Computer Science 2005 20 Pages PDF
Abstract
The strong Rabin number of a network W of connectivity k is the minimum l so that for any k+1 nodes s, d1,d2,…,dk of W, there exist k node-disjoint paths from s to d1,d2,…,dk, respectively, whose maximal length is not greater than l, where s∉{d1,d2,…,dk} and d1,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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,