An Optimal Construction of Node-Disjoint Shortest Paths in

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(mn1.5) time, where mn. The worst-case time complexity and space complexity of the construction procedure are both O(mn), which is optimal and hence improves previous results. In the situation that all of the source node and destination nodes are mutually distinct, experiment results show that the probability that there exist node-disjoint shortest paths (from the source node to the destination nodes) is greater than 87%, 89%, 91%, and 94 % for m=n=4, 5, 6, and 7, respectively.