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

### MAXIMUM MINIMUM SPANNING TREE DELETING K EDGES

- INSTANCE: Graph , a weight function .

- SOLUTION: Subset of k edges and a minimum spanning tree T in the graph .

- MEASURE: Weight of T.

- Good News: Approximable within [162].

- Comment: The good news is valid even if a minimum -edge connected subgraph of G is sought, for every [162].