Next:
ND3 MINIMUM GEOMETRIC
Up:
Spanning Trees
Previous:
ND1 MINIMUM K-SPANNING
-
I
NSTANCE
:
Graph
.
-
S
OLUTION
:
A spanning tree for
G
.
-
M
EASURE
:
The maximum degree of the spanning graph.
-
Good News:
Approximable with an absolute error guarantee of 1 [
117
].
-
Bad News:
Not approximable within 3/2
for any
[
121
].
-
Comment:
A
PX
-intermediate unless the polynomial-hierarchy collapses
[
85
].
The generalization of the problem to Steiner trees is also
approximable with an absolute error guarantee of 1 [
117
].
-
Garey and Johnson:
ND1
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997