Name
Abstract | ||
|---|---|---|
The w-Rabin number of a network W is the minimum l so that for any w + 1 distinct nodes s, d1,d2,…,dw of W, there exist w node-disjoint paths from s to d1,d2,…,dw, respectively, whose maximal length is not greater than l, where w is not greater than the node connectivity of W. If {d1,d2,…,dw} is allowed to be a multiset, then the resulting minimum l is called the strong w-Rabin number of W. In this article, we show that both the w-Rabin number and the strong w-Rabin number of a k-dimensional folded hypercube are equal to ⌈k-2⌉ for 1 ≤ w ≤ ⌈k-2⌉- 1, and ⌈k-2⌉+ 1 for ⌈k-2⌉ ≤ w ≤ k + 1, where k ≥ 5. Each path obtained is shortest or second shortest. The results of this paper also solve an open problem raised by Liaw and Chang. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008 |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1002/net.v51:3 | Networks |
Keywords | Field | DocType |
optimization problem,hypercube | Discrete mathematics,Combinatorics,Open problem,Shortest path problem,Multiset,Multiplicity (mathematics),Optimization problem,Hypercube,Mathematics | Journal |
Volume | Issue | ISSN |
51 | 3 | 0028-3045 |
Citations | PageRank | References |
10 | 0.66 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cheng-Nan Lai | 1 | 70 | 6.95 |
| Gen-Huey Chen | 2 | 979 | 89.32 |