论文标题
从最短的线性上线到最短的圆形超弦，贪婪减少了
Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring
论文作者
论文摘要
一组字符串的超声词对应于一个包含所有其他字符串作为子字符串的字符串。找到最短的线性超弦的问题是弦乐学方面的知识良好且研究的问题。我们在这里提出了这个问题的变体，这是最短的圆形超串件问题，在该问题中，寻求的超弦是一个圆形的弦。我们在这两个问题之间表现出牢固的联系，并证明最短的圆形超边缘问题是NP完整的。此外，我们提出了一个新的猜想，即最短的圆形超串问题的近似比。
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.
