Next: MINIMUM EDGE 2-SPANNER
Up: Subgraphs and Supergraphs
Previous: MAXIMUM SUBFOREST
  Index
- INSTANCE:
Graph
,
a weight function
,
and positive integer k.
- SOLUTION:
A subset
such that |V'|=k.
- MEASURE:
Total weight of the edges in the subgraph induced by V', i.e.,
- Good News:
Approximable within
for some
[317] and [145].
- Comment:
Also called Heaviest Subgraph.
Approximable within 2 if the weights satisfy the triangle inequality
[224].
The unweighted problem admits a PTAS if
and
[37].
Viggo Kann
1999-04-22