Optimal One-to-Many Disjoint Paths in Folded Hypercubes.
Journal
5th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2000), 7-10 December 2000, Dallas / Richardson, TX, USA
Pages
148-155
Date Issued
2000
Author(s)
Abstract
Routing functions have been shown to be effective in deriving disjoint paths in the hypercube. In this paper, by the aid of a minimal routing function, k+1 disjoint paths from one node to another k+1 distinct nodes are constructed in the folded hypercube whose maximal length is not greater than [k/2]+1, where k is the dimension and [k/2] is the diameter of the folded hypercube. The maximal length is minimized in the worst case. For the general case, the maximal length is nearly optimal (/spl les/ the maximal distance between the two end nodes of these k+1 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 (1999).
Type
conference paper