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(mn(1.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 them 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. (C) 2016 Elsevier Inc. All rights reserved.