Routing Functions-an Effective Approach to Deriving One-to-Many Disjoint Paths
Date Issued
2000
Date
2000
Author(s)
DOI
20060927122858960607
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, a maximal number of disjoint paths whose
maximal length is minimized in the worst case can be constructed in the hypercube and the folded hypercube.
The end nodes of the paths constructed for the hypercube are not necessarily distinct. As a byproduct, the
strong Rabin number of the hypercube and the Rabin number of the folded hypercube are computed. The
latter provides a solution to an open problem raised by Liaw and Chang. A maximal number of disjoint
paths whose total length is minimized can also be constructed in the hypercube by the use of a routing
function.
Subjects
Disjoint paths
folded hypercube
hypercube
optimization problem
Rabin number
strong Rabin number
Publisher
臺北市:國立臺灣大學資訊工程學系
Type
other
File(s)![Thumbnail Image]()
Loading...
Name
ntucsie00-02.pdf
Size
320.07 KB
Format
Adobe PDF
Checksum
(MD5):95025c2a29291f9d5d96b664188be8c9