Next: MAXIMUM MINIMUM SPANNING TREE
Up: Spanning Trees
Previous: MINIMUM GENERALIZED STEINER NETWORK
and a weight function
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.
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
- Good News:
- Bad News:
Not in APX .
The algorithm extends to the case when the routing tree is allowed to have
vertices of higher degree.
If G is planar , or
if T is required to be a spanning tree and G is
complete , the problem is solvable in polynomial time.