A superstring of a set of strings correspond to a string which contains all the other strings as substrings. The problem of finding the Shortest Linear Superstring is a well-know and well-studied problem in stringology. We present here a variant of this problem, the Shortest Circular Superstring problem where the sought superstring is a circular string. We show a strong link between these two problems and prove that the Shortest Circular Superstring problem is NP-complete. Moreover, we propose a new conjecture on the approximation ratio of the Shortest Circular Superstring problem.
翻译：一组字符串的超级字符串与包含所有其他字符串作为子字符串的字符串相对应。 找到最短线条超级字符串的问题在字符串学上是一个广为人知和研究周密的问题。 我们在此提出这一问题的变体, 即所寻求的超字符串是圆字符串的最短圆条超级字符串的超级字符串问题。 我们显示了这两个问题之间的紧密联系, 并证明最短的圆条超级字符串问题是NP- 完整的。 此外, 我们建议对最短的圆条超级字符串问题的近似比重进行新的猜测 。
相关内容
微信扫码咨询专知VIP会员