Next: MINIMUM STEINER TREE
Up: Spanning Trees
Previous: MINIMUM DIAMETER SPANNING SUBGRAPH
  Index
- 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 [397].
- Comment:
MINIMUM ROUTING COST SPANNING TREE, the variation in which
for all u,v, admits a PTAS [469].
- Garey and Johnson: ND7
Viggo Kann
2000-03-20