Computer Science – Data Structures and Algorithms
Scientific paper
2002-05-30
Information Processing Letters 50:49-55 (1994)
Computer Science
Data Structures and Algorithms
Conference version in WADS'93
Scientific paper
The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands. This paper considers the multi-commodity flow network-design problem: given a set of multi-commodity flow demands, find a network subject to certain constraints such that the commodities can be maximally routed. This paper focuses on the case when the network is required to be a tree. The main result is an approximation algorithm for the case when the tree is required to be of constant degree. The algorithm reduces the problem to the minimum-weight balanced-separator problem; the performance guarantee of the algorithm is within a factor of 4 of the performance guarantee of the balanced-separator procedure. If Leighton and Rao's balanced-separator procedure is used, the performance guarantee is O(log n). This improves the O(log^2 n) approximation factor that is trivial to obtain by a direct application of the balanced-separator method.
Khuller Samir
Raghavachari Balaji
Young Neal E.
No associations
LandOfFree
Designing Multi-Commodity Flow Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Designing Multi-Commodity Flow Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Designing Multi-Commodity Flow Trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-100446