Next: MAXIMUM PLANAR SUBGRAPH
Up: Subgraphs and Supergraphs
Previous: MINIMUM VERTEX DELETION TO
  Index
- INSTANCE:
Graph
,
a weight function
,
and an integer
.
- SOLUTION:
A subset
such that the subgraph
is connected and has no vertex with degree exceeding d.
- MEASURE:
The total weight of the subgraph, i.e.,
.
- Bad News:
Not in APX for any d [Kann, --].
- Comment:
Transformation from LONGEST PATH. The problems have, indeed, the same
non-approximability results.
- Garey and Johnson: GT26
Viggo Kann
1999-04-22