Optimal one-to-many disjoint paths in folded hypercubes
Cheng‐Nan Lai, Gen-Huey Chen, Dyi‐Rong Duh · 2002
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).