Strong Rabin numbers of folded hypercubes
Resource
Theoretical Computer Science,341(1),196-215.
Theoretical Computer Science 341(2005), 196â 215
Journal
Theoretical Computer Science
Pages
-
Date Issued
2005
Date
2005
Author(s)
Lai, Cheng-Nan
DOI
246246/2006111501244229
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.
Subjects
Folded hypercube
Hypercube
Node-disjoint paths
Optimization problem
Strong Rabin number
Publisher
Taipei:National Taiwan University Dept Chem Engn
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
2635.pdf
Size
23.19 KB
Format
Adobe PDF
Checksum
(MD5):a72949552b602afb79190ac2f7646670