Next:
GT29 MAXIMUM PLANAR
Up:
Subgraphs and Supergraphs
Previous:
GT27 MINIMUM VERTEX
GT28 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
Mon Apr 21 13:07:14 MET DST 1997
, a weight function
,
and an integer
.
such that the subgraph
is connected and has no vertex with degree exceeding
d
.
.