TY - GEN

T1 - Designing multi-commodity flow trees

AU - Khuller, Samir

AU - Raghavachari, Balaji

AU - Young, Neal

N1 - Funding Information:
We consider the case when the network is required to be a tree, called the tree congestion problem. Given a tree in which the vertices of G are embedded, the load on an edge e is defined as follows: delete e from T. This breaks T into two connected "Department of Computer Science, University of Maryland, College Park, MD 20742. E-mail : s amir@r umd. edu. tComputer Science Department, Pennsylvania State University, University Park, PA 16802. E-mail : :rbkQcs. psu. edu. Part of this work was done while this author was visiting UMIACS. lInstitute for Advanced Computer Studies, University of Maryland, College Park, MD 20742. E-mail : you.ugCm~iacs.umd.eda. Research supported in part by NSF grants CCR-8906949 and CCK-9111348.

PY - 1993

Y1 - 1993

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=21144482001&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21144482001&partnerID=8YFLogxK

U2 - 10.1007/3-540-57155-8_268

DO - 10.1007/3-540-57155-8_268

M3 - Conference contribution

AN - SCOPUS:21144482001

SN - 9783540571551

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 433

EP - 441

BT - Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Santoro, Nicola

A2 - Whitesides, Sue

PB - Springer Verlag

T2 - 3rd Workshop on Algorithms and Data Structures, WADS 1993

Y2 - 11 August 1993 through 13 August 1993

ER -