Routing functions had been shown effective in constructing node-disjoint paths in hypercube-like networks. In this paper, by the aid of routing functions, m node-disjoint shortest paths from one source node to other m (not necessarily distinct) destination nodes are constructed in an n-dimensional hypercube, provided the existence of such node-disjoint shortest paths which can be verified in O(mn^{1.5}) time, where {m} \leq {n}. The construction procedure has worst case time complexity O(mn), which is optimal and hence improves previous results. By taking advantages of the construction procedure, m node-disjoint paths from one source node to other m (not necessarily distinct) destination nodes in an n-dimensional hypercube such that their total length is minimized can be constructed in O(mn^{1.5} + {m}^3{n}) time, which is more efficient than the previous result of O(m^2 {n}^{2.5} + {mn}^3) time. Besides, their maximal length is also minimized in the worst case.

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

Routing functions have been shown effective in deriving disjoint paths in the hypercube. In this paper, using a minimal routing function, k+1 disjoint paths from one node to another k+1 distinct nodes are constructed in a k-dimensional folded hypercube whose maximal length is not greater than the diameter plus one, which is minimum in the worst case. For the general case, the maximal length is nearly optimal (/spl les/ the maximal distance between the two end nodes of these k+1 paths plus two). As a by-product, the Rabin number of the folded hypercube is obtained, which is an open problem raised by S.C. Liaw and G.J. Chang (1999).