Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657801 | Theoretical Computer Science | 2005 | 20 Pages |
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
Cheng-Nan Lai, Gen-Huey Chen,