One-to-Many Disjoint Paths in Hypercubes

Abstract

This paper introduces a new concept called routing functions, which have a close relation to one-to-many disjoint paths in networks. By using a minimal routing function, m disjoint paths whose maximal length is minimized in the worst case can be obtained in a k-dimensional hypercube, where m£k. Besides, there exist routing functions that can be used to construct m disjoint paths whose total length is minimized. The end nodes of these paths are not necessarily distinct. A minimal routing function can also be used to construct a maximal number of disjoint paths in the folded hypercube whose maximal length is minimized in the worst case.