MINIMUM DIAMETER SPANNING SUBGRAPH

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

INSTANCE: Graph $G=\left(V,E\right)$ , weight $w(e)\in Z^+$ and length $l(e)\in N$ for each $e\in E$ , positive integer B.
SOLUTION: A spanning subgraph $E'\subseteq E$ 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 $-\varepsilon$ for any $\varepsilon >0$ [405].
Comment: Not approximable within 3/2 $-\varepsilon$ for planar graphs. Not approximable within 5/4 $-\varepsilon$ 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