Optimal construction of node-disjoint shortest paths in folded hypercubes

Node-disjoint paths have played an important role in the study of routing, reliability, and fault tolerance of an interconnection network. In this paper, we give a necessary and sufficient condition, which can be verified in O(mn1.5) time, for the existence of m node-disjoint shortest paths from one source node to other m (not necessarily distinct) target nodes, respectively, in an n-dimensional folded hypercube, where m≤n+1. Moreover, when the condition holds, the m node-disjoint shortest paths can be constructed in optimal O(mn) time. In the situation that all of the source node and target nodes are mutually distinct, brute-force computations show that the probability of existence of the m node-disjoint shortest paths in an n-dimensional folded hypercube is not less than 100%, 86%, 86%, 92%, and 94% for (n,m)=(3,4),(4,4),(5,6),(6,6), and (7, 8), respectively.