Next: MINIMUM COMMUNICATION COST SPANNING Up: Spanning Trees Previous: MAXIMUM MINIMUM METRIC K-SPANNING Index

### MINIMUM DIAMETER SPANNING SUBGRAPH

- 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 [384].

- Comment: Not approximable within 3/2 for planar graphs. Not approximable within 5/4 if l(e)=1 for every edge e [384]. For results on minimum Steiner trees of bounded diameter, see MINIMUM STEINER TREE.

- Garey and Johnson: Similar to ND4