The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 24 NO.5 / (1995))
On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
Tao Jiang, Ming Li,
Pages. 1122-1139
Abstract
Contents 1. Introduction
2. Recent works on the complexity of approximation
3. Nonapproximability of SCS and LCS
3.1. Approximating LSC is hard
3.2. Restricted versions of SCS and MAX SNP-hardness
3.3. The product of sets of sequences
3.4. SCS has no linear approximation algorithms
4. Algorithms with good average-case performance
4.1. Kolmogorov complexity
4.2. Longest common subsequneces: The average case
4.3. Shortest common supersequneces: The average case
5. Some remarks
Key words shortest common supersequence, longest common subsequence, approximation algorithm, $\mathbf {NP}$-hardness, average-case analysis, random sequence.
Mathmatical Subject Classification 68Q20, 68Q25