Affordable Access

Publisher Website

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
  • Hypercube
  • Folded Hypercube
  • Node-Disjoint Paths
  • Matching Problem
  • Optimization Problem
Disciplines
  • Computer Science

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.