Maximal Common Subsequences and Minimal Common Supersequences
Maximal Common Subsequences and Minimal Common Supersequences
复制标题
最大公共子序列和最小公共超序列
DOI：
--
复制
发表时间：
1994
影响因子：
1
通讯作者：
M. Middendorf
中科院分区：
文献类型：
--
作者：
Campbell Fraser;Robert W. Irving;M. Middendorf
寻找一组字符串的最长公共子序列和最短公共超序列的问题是众所周知的。对于两个字符串(实际上在这种情况下问题是对偶的)，或者对于任意固定数量的字符串，可以通过动态规划在多项式时间内解决它们。但是，对于任意数量的k个字符串，这两个问题通常都是NP难的。这里我们研究了寻找最小长度最大公共子序列和最大长度最小公共超序列的相关问题。我们描述了两个字符串的情况下的动态规划算法(在这种情况下，问题不再是对偶问题)，它可以扩展到任意固定数量的字符串。我们还证明了对于k个串，最小最大公共子序列问题一般是NP-难的，并且证明了该问题的一个强负逼近性结果。一般k的最大最小公共超序列问题的复杂性仍然是开放的，尽管我们猜想它也是NP-难的。
The problems of finding a longest common subsequence and a shortest common supersequence of a set of strings are well-known. They can be solved in polynomial time for two strings (in fact the problems are dual in this case), or for any fixed number of strings, by dynamic programming. But both problems are NP-hard in general for an arbitrary number k of strings. Here we study the related problems of finding a minimum-length maximal common subsequence and a maximum-length minimal common supersequence. We describe dynamic programming algorithms for the case of two strings (for which case the problems are no longer dual), which can be extended to any fixed number of strings. We also show that the minimum maximal common subsequence problem is NP-hard in general for k strings, and we prove a strong negative approximability result for this problem. The complexity of the maximum minimal common supersequence problem for general k remains open, though we conjecture that it too is NP-hard.