Next: MAXIMUM MINIMUM SPANNING TREE Up: Spanning Trees Previous: MINIMUM GENERALIZED STEINER NETWORK Index

### MINIMUM ROUTING TREE CONGESTION

- 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 [297].

- Bad News: Not in APX [413].

- Comment: The algorithm extends to the case when the routing tree is allowed to have vertices of higher degree. If G is planar [413], or if T is required to be a spanning tree and G is complete [297], the problem is solvable in polynomial time.