Next:
ND4 MAXIMUM LEAF
Up:
Spanning Trees
Previous:
ND2 MINIMUM DEGREE
-
I
NSTANCE
:
Set
of points in the plane.
-
S
OLUTION
:
A spanning tree
T
for
P
in which no vertex has degree larger than 3.
-
M
EASURE
:
The total weight of the spanning tree, i.e.,
,
where
d(u,v)
is the Euclidean distance between
u
and
v
.
-
Good News:
Admits a PTAS [
19
].
-
Comment:
The 4-degree spanning tree problem also admits a PTAS, but the NP-hardness
of the problem is open [
19
].
The 5-degree problem is polynomial-time solvable.
In
d
-dimensional Euclidean space for
the 3-degree spanning tree
problem is approximable within 5/3. [
225
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997