Next: MINIMUM ATTRACTION RADIUS FOR
Previous: MINIMUM TREE ALIGNMENT
Finite alphabet ,
finite string s from .
A folding of s in the 3-dimensional rectangular grid ,
that is, a mapping of s into
such that adjacent symbols
of s are adjacent in the lattice, and no site in the lattice is
occupied by more than one symbol.
The number of pairs of equal symbols that lie at adjacent
lattice sites (excluding pairs that are adjacent in s).
- Bad News:
APX-hard under randomized polynomial time reductions .