An efficient construction of one-to-many node-disjoint paths in folded hypercubes

• A most efficient method for finding optimal node-disjoint paths in folded hypercubes.
• Finding optimal node-disjoint paths is dominated by finding maximum matchings.
• Routing functions are an effective technology for constructing node-disjoint paths.

A folded hypercube is basically a hypercube with additional links augmented, where the additional links connect all pairs of nodes with longest distance in the hypercube. In an nn-dimensional folded hypercube, it has been shown that n+1n+1 node-disjoint paths from one source node to other n+1n+1 (mutually) distinct destination nodes, respectively, can be constructed in O(n4)O(n4) time so that their maximal length is not greater than ⌈n/2⌉+1⌈n/2⌉+1, where n+1n+1 is the connectivity and ⌈n/2⌉⌈n/2⌉ is the diameter. Besides, their maximal length is minimized in the worst case. In this paper, we further show that by minimizing the computations of minimal routing functions, these node-disjoint paths can be constructed in O(n3)O(n3) time, which is more efficient, and is hard to be reduced because it must take O(n3)O(n3) time to compute a minimal routing function by solving a corresponding maximum weighted bipartite matching problem with the best known algorithm.