THE SHORTEST COMMON SUPERSEQUENCE PROBLEM OVER BINARY ALPHABET IS NP-COMPLETE

被引：75

作者：

RAIHA, KJ

UKKONEN, E

机构：

来源：

关键词：

D O I：

10.1016/0304-3975(81)90075-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：187 / 198

页数：12

共 7 条

[1]

AHO AV, 1976, J ACM, V23, P1, DOI 10.1145/321921.321922

[2]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

[3]

Garey Michael R., 1979, COMPUTERS INTRACTABI

[4]

Karp R.M., 1972, COMPLEXITY COMPUTER

[5] COMPLEXITY OF SOME PROBLEMS ON SUBSEQUENCES AND SUPERSEQUENCES [J].

MAIER, D .

[6]

RAIHA KJ, UNPUBLISHED

[7] STRING-TO-STRING CORRECTION PROBLEM [J].

WAGNER, RA ;

FISCHER, MJ .