MAXIMUM MINIMUM SPANNING TREE DELETING K EDGES

Next: MINIMUM UPGRADING SPANNING TREE Up: Spanning Trees Previous: MINIMUM ROUTING TREE CONGESTION Index

INSTANCE: Graph $G=\left(V,E\right)$ , a weight function $w : E \rightarrow N$ .
SOLUTION: Subset $E'\subseteq E$ of k edges and a minimum spanning tree T in the graph $\left(V,E-E'\right)$ .
MEASURE: Weight of T.
Good News: Approximable within $\log k$ [174].
Comment: The good news is valid even if a minimum $\lambda$ -edge connected subgraph of G is sought, for every $\lambda\ge 1$ [174].

Viggo Kann
2000-03-20