TY - GEN

T1 - On shortest common superstring and swap permutations

AU - Gotthilf, Zvi

AU - Lewenstein, Moshe

AU - Popa, Alexandru

N1 - Funding Information:
★ This work was partially supported by the Israel Science Foundation grant 1484/08.
Funding Information:
Acknowledgements. We thank the anonymous reviewers for their useful comments. The third author is funded by an EPSRC PhD studentship.

PY - 2010

Y1 - 2010

N2 - The Shortest Common Superstring (SCS) is a well studied problem, having a wide range of applications. In this paper we consider two problems closely related to it. First we define the Swapped Restricted Superstring(SRS) problem, where we are given a set S of n strings, s1, s2, ..., sn , and a text T=t1 t2 ...tm , and our goal is to find a swap permutation π: {1, ..., m} →{1, ..., m} to maximize the number of strings in S that are substrings of tπ(1) tπ(2)...tπ(m). We then show that the SRS problem is NP-Complete. Afterwards, we consider a similar variant denoted SRSR, where our goal is to find a swap permutation π: {1, ..., m} →{1, ..., m} to maximize the total number of times that the strings of S appear in t π(1) tπ(2)...tπ(m) (we can count the same string si as a substring of tπ(1) t π(2)...tπ(m) more than once). For this problem, we present a polynomial time exact algorithm.

AB - The Shortest Common Superstring (SCS) is a well studied problem, having a wide range of applications. In this paper we consider two problems closely related to it. First we define the Swapped Restricted Superstring(SRS) problem, where we are given a set S of n strings, s1, s2, ..., sn , and a text T=t1 t2 ...tm , and our goal is to find a swap permutation π: {1, ..., m} →{1, ..., m} to maximize the number of strings in S that are substrings of tπ(1) tπ(2)...tπ(m). We then show that the SRS problem is NP-Complete. Afterwards, we consider a similar variant denoted SRSR, where our goal is to find a swap permutation π: {1, ..., m} →{1, ..., m} to maximize the total number of times that the strings of S appear in t π(1) tπ(2)...tπ(m) (we can count the same string si as a substring of tπ(1) t π(2)...tπ(m) more than once). For this problem, we present a polynomial time exact algorithm.

UR - http://www.scopus.com/inward/record.url?scp=78449306564&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78449306564&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-16321-0_28

DO - 10.1007/978-3-642-16321-0_28

M3 - Conference contribution

AN - SCOPUS:78449306564

SN - 3642163203

SN - 9783642163203

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 270

EP - 278

BT - String Processing and Information Retrieval - 17th International Symposium, SPIRE 2010, Proceedings

T2 - 17th International Symposium on String Processing and Information Retrieval, SPIRE 2010

Y2 - 11 October 2010 through 13 October 2010

ER -