- INSTANCE:
Graph
and a weight function
.
- SOLUTION:
A routing tree
*T*for*G*, i.e., a tree*T*in which each internal vertex has degree 3 and the leaves correspond to vertices of*G*. - MEASURE:
The congestion of the routing tree, i.e., the maximum, for any
edge
*e*, of

where*S*is one of the two connected components obtained by deleting*e*from*T*.

*Good News:*Approximable within [314].*Bad News:*Not in APX [436].*Comment:*The algorithm extends to the case when the routing tree is allowed to have vertices of higher degree. If*G*is planar [436], or if*T*is required to be a spanning tree and*G*is complete [314], the problem is solvable in polynomial time.