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

Pages. 1122-1139
Abstract 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 shortest common supersequence, longest common subsequence, approximation algorithm, $\mathbf {NP}$-hardness, average-case analysis, random sequence. 68Q20, 68Q25