Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)
MAXIMUM MINIMUM SPANNING TREE DELETING K EDGES
Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)
Next: MINIMUM UPGRADING SPANNING TREE
Up: Spanning Trees
Previous: MINIMUM ROUTING TREE CONGESTION
  Index
- 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
[174].
- Comment:
The good news is valid even if a minimum
-edge connected
subgraph of G is sought, for every
[174].
Viggo Kann
2000-03-20