Next:
MAXIMUM PLANAR SUBGRAPH
Up:
Subgraphs and Supergraphs
Previous:
MINIMUM VERTEX DELETION TO
 
Index
M
AXIMUM
D
EGREE-
B
OUNDED
C
ONNECTED
S
UBGRAPH
I
NSTANCE:
Graph
, a weight function
, and an integer
.
S
OLUTION:
A subset
such that the subgraph
is connected and has no vertex with degree exceeding
d
.
M
EASURE:
The total weight of the subgraph, i.e.,
.
Bad News:
Not in A
PX
for any
d
[Kann, --].
Comment:
Transformation from L
ONGEST
P
ATH
. The problems have, indeed, the same non-approximability results.
Garey and Johnson:
GT26
Viggo Kann
2000-03-20