Next: MAXIMUM COMMON SUBTREE
Up: Compression and Representation
Previous: SHORTEST COMMON SUPERSTRING
  Index
- INSTANCE:
Finite alphabet
,
finite set R of strings from
.
- SOLUTION:
A string
such that w is a subsequence of each
,
i.e. one can get w by taking away letters from each x.
- MEASURE:
Length of the subsequence, i.e., |w|.
- Good News:
Approximable within
,
where m is the length of the
shortest string in R [210].
- Bad News:
Not approximable within
for any
,
where n is the maximum of |R| and
[71], [260] and [63].
- Comment:
Transformation from MAXIMUM INDEPENDENT SET.
APX-complete if the size of the alphabet
is fixed [260]
and [82].
Variation in which the objective is to find the shortest maximal common
subsequence (a subsequence that cannot be extended to a longer common
subsequence) is not approximable within
for
any
[157].
- Garey and Johnson: SR10
Viggo Kann
1999-04-22