Constructing all shortest node-disjoint paths in torus networks

• An optimal construction of all shortest node-disjoint paths in a torus network.
• High probability of the existence of disjoint shortest paths in a torus was shown.
• Finding disjoint shortest paths in a torus is equivalent to that in a hypercube.

An nn-dimensional torus network, also called wrap-around mesh or toroidal network, is a Cartesian product of nn cycle networks. In particular, it was named kk-ary nn-cube when the sizes of the nn cycle networks are all equal to kk. In this paper, mm node-disjoint shortest paths from one source node to other mm (not necessarily distinct) destination nodes are constructed in an nn-dimensional torus network, provided the existence of such node-disjoint shortest paths which can be verified in O(mn1.5)O(mn1.5) time, where mm is not greater than the connectivity. The worst-case time and space complexities of the construction procedure are both optimal O(mn)O(mn). In the situation that all of the source node and destination nodes are mutually distinct, brute-force computations show that the probability of the existence of the mm node-disjoint shortest paths (from the source node to the mm destination nodes) in a kk-ary nn-cube is greater than 94%, 70%, 91%, 69%, and 89% for (k,n,m)=(2,7,7)(k,n,m)=(2,7,7), (3, 4, 8), (4, 3, 6), (5, 3, 6), and (6, 3, 6), respectively.