Next: MINIMUM COMMUNICATION COST SPANNING
Up: Spanning Trees
Previous: MAXIMUM MINIMUM METRIC K-SPANNING
  Index
- INSTANCE:
Graph
,
weight
and length
for each ,
positive integer B.
- SOLUTION:
A spanning subgraph
for G such that the sum of the weights
of the edges in E' does not exceed B.
- MEASURE:
The diameter of the spanning subgraph.
- Bad News:
Not approximable within 2
for any
[405].
- Comment:
Not approximable within 3/2
for planar graphs.
Not approximable within 5/4
if l(e)=1 for every edge e
[405].
For results on minimum Steiner trees of bounded diameter, see MINIMUM STEINER TREE.
- Garey and Johnson: Similar to ND4
Viggo Kann
2000-03-20