Next:
References
Up:
Miscellaneous
Previous:
MS13 MINIMUM PHYLOGENETIC
-
I
NSTANCE
:
Graph
, and, for each node
u
, a finite set
of available frequencies and two integers
.
-
S
OLUTION
:
A frequency allocation for
G
, i.e., for each node
u
, a subset
S(u)
of
L(u)
such that, for all
,
, and, for all
,
.
-
M
EASURE
:
The stability number of the allocation, i.e.,
.
-
Good News:
Approximable within 2 [
267
].
-
Bad News:
A
PX
-complete [
267
].
-
Comment:
Reduction from M
AXIMUM
3-S
ATISFIABILITY
.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997