Next: Cuts and Connectivity Up: Spanning Trees Previous: MAXIMUM MINIMUM SPANNING TREE Index

### MINIMUM UPGRADING SPANNING TREE

- INSTANCE: Graph G=(V,E), three edge weight functions (for each ), where di(e) denotes the weight of edge e if i of its endpoints are ``upgraded'', vertex upgrade costs c(v) (for each ), a threshold value D for the weight of a minimum spanning tree.

- SOLUTION: An upgrading set of vertices such that the weight of a minimum spanning tree in G with respect to edge weights given by dW is bounded by D. Here, dW denotes the edge weight function resulting from the upgrade of the vertices in W, i.e., dW(u,v)=di(u,v) where .

- MEASURE: The cost of the upgrading set, i.e., .

- Good News: Approximable within if the difference of the largest edge weight and the smallest edge weight is bounded by a polynomial in |V| [326].

- Bad News: At least as hard to approximate as MINIMUM DOMINATING SET [326].

- Comment: Variation in which the upgrading set must be chosen such that the upgraded graph contains a spanning tree in which no edge has weight greater than D is approximable within . In this case no additional assumptions about the edge weights are necessary. This variation of the problem is also at least as hard to approximate as MINIMUM DOMINATING SET [326].

Next: Cuts and Connectivity Up: Spanning Trees Previous: MAXIMUM MINIMUM SPANNING TREE Index