Optimal node-disjoint paths in folded hypercubes

The constructions of node-disjoint paths have been well applied to the study of connectivity, diameter, parallel routing, reliability, and fault tolerance of an interconnection network. In order to minimize the transmission cost and latency, the total length and maximal length of the node-disjoint paths should be minimized, respectively. The construction of node-disjoint paths with their maximal length minimized (in the worst case) has been studied previously in folded hypercubes. In this paper, we construct m node-disjoint paths from one source node to other m (not necessarily distinct) target nodes, respectively, in an n-dimensional folded hypercube so that both of their total length and maximal length (in the worst case) are minimized, where m <= n+1. In addition, each path is either shortest or nearly shortest. The construction of these node-disjoint paths can be efficiently carried out in 0(mn(1.5) + m(3)n) and O(mn(2) + n(2) logn+m(3) n) time, respectively, for odd and even rt by taking advantage of two specific routing functions, which provide another strong evidence for the effective applications of routing functions in deriving node-disjoint paths, especially for the variants of hypercubes. (C) 2020 Elsevier Inc. All rights reserved.

Automated summary

The study in this paper focuses on constructing m node-disjoint paths in a folded hypercube to minimize the total length and maximal length, where m <= n+1. By utilizing two specific routing functions, the construction of these paths can be efficiently carried out for odd and even routing, providing strong evidence for the effective applications of routing functions in deriving node-disjoint paths.