2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00)
Optimal One-to-Many Disjoint Paths in Folded Hypercubes
Dallas/Richardson, Texas, USA
December 07-December 07
ISBN: 0-7695-0936-3
Routing functions have been shown effective in deriving disjoint paths in the hypercube. In this paper, by the aid of a minimal routing function, k+l disjoint paths from one node to another k+l distinct nodes are constructed in the folded hypercube whose maximal length is not greater than [k/21+1, where k is the dimension and [k/21 is the diameter of the folded hypercube. The maximal length is minimized in the worst case. For general case, the maximal length is nearly optimal (I the maximal distance between the two end nodes of these k+l paths plus two). The result of this paper also computes the Rabin number of the folded hypercube, which is an open problem raised by Liaw and Chang.
Citation:
C.-N. Lai, G.-H. Chen, D.-R. Duh, "Optimal One-to-Many Disjoint Paths in Folded Hypercubes," ispan, pp.148, 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), 2000