Next: SHORTEST PATH MOTION IN
Up: Miscellaneous
Previous: MINIMUM SORTING BY REVERSALS
  Index
- INSTANCE:
Set
of variables taking values from the sets
respectively, binary compatibility constraints
for .
- SOLUTION:
A compatible variable assignment to a subset of the variables such that
for all pairs
of variables in the subset, the corresponding
values
.
- MEASURE:
The number of variables in the compatible variable assignment.
- Bad News:
Not approximable within
for any
[268] and [68].
- Comment:
Equivalent to MAXIMUM CLIQUE under PTAS-reduction [268].
Viggo Kann
2000-03-20