Next:
ND2 MINIMUM DEGREE
Up:
Spanning Trees
Previous:
Spanning Trees
-
I
NSTANCE
:
Graph
, an integer
, and a weight function
.
-
S
OLUTION
:
A
k
-spanning tree, i.e., a subtree
T
of
G
of at least
k
nodes.
-
M
EASURE
:
The weight of the tree, i.e.,
.
-
Good News:
Approximable within 3 [
123
].
-
Comment:
The restriction to points in the Euclidean plane admits a PTAS
[
19
].
The analogous diameter and communication-cost
k
-spanning tree problems are
not in A
PX
[
309
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997