Next: MAXIMUM MINIMUM SPANNING TREE
Up: Spanning Trees
Previous: MINIMUM GENERALIZED STEINER NETWORK
  Index
- 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.
Viggo Kann
2000-03-20