Next: Cuts and Connectivity
Up: Spanning Trees
Previous: MAXIMUM MINIMUM SPANNING TREE
  Index
- 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
Viggo Kann
1999-04-22