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

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 n-dimensional folded hypercube, it has been shown that n + 1 node-disjoint paths from one source node to other n + 1 (mutually) distinct destination nodes, respectively, can be constructed in O(n(4)) time so that their maximal length is not greater than [n/2] + 1, where n 1 is the connectivity and [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(n(3)) time, which is more efficient, and is hard to be reduced because it must take O(n(3)) time to compute a minimal routing function by solving a corresponding maximum weighted bipartite matching problem with the best known algorithm. (C) 2013 Elsevier Inc. All rights reserved.