Next: MINIMUM STEINER TREE Up: Spanning Trees Previous: MINIMUM DIAMETER SPANNING SUBGRAPH Index

### MINIMUM COMMUNICATION COST SPANNING TREE

- INSTANCE: Complete graph , weight for each , requirement for each pair of vertices from V.

- SOLUTION: A spanning tree for G.

- MEASURE: The weighted sum over all pairs of vertices of the cost of the path between the pair in T, i.e., , where W(u,v) denotes the sum of the weights of the edges on the path joining u and v in T.

- Good News: Approximable within if the weight function satisfies the triangle inequality [375].

- Comment: MINIMUM ROUTING COST SPANNING TREE, the variation in which for all u,v, admits a PTAS [446].

- Garey and Johnson: ND7