On the construction of all shortest node-disjoint paths in star networks

• An optimal construction of all shortest node-disjoint paths in a star network.
• High probability of the existence of disjoint shortest paths was shown.
• A sufficient condition for the existence of disjoint shortest paths was given.

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 sufficient condition, which can be verified in O(mn1.5)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 star network, where m≤n−1m≤n−1 and n≥3n≥3. In addition, when the condition holds, the m   node-disjoint shortest paths can be constructed in optimal O(mn)O(mn) time. By the aid of the sufficient condition, the probability of existence of all shortest node-disjoint paths was also evaluated for some special cases.