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

- Authors
- Journal
- Journal of Parallel and Distributed Computing 0743-7315
- Publisher
- Elsevier
- Volume
- 74
- Issue
- 4
- Identifiers
- DOI: 10.1016/j.jpdc.2013.12.005
- Keywords
- Disciplines

## Abstract

Abstract 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(n4) 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(n3) time, which is more efficient, and is hard to be reduced because it must take O(n3) time to compute a minimal routing function by solving a corresponding maximum weighted bipartite matching problem with the best known algorithm.

## There are no comments yet on this publication. Be the first to share your thoughts.