On shortest common superstring and swap permutations

Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages270-278
Number of pages9
Volume6393 LNCS
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event17th International Symposium on String Processing and Information Retrieval, SPIRE 2010 - Los Cabos, Mexico
Duration: Oct 11 2010Oct 13 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6393 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other17th International Symposium on String Processing and Information Retrieval, SPIRE 2010
CountryMexico
CityLos Cabos
Period10/11/1010/13/10

Fingerprint

Superstring
Swap
Computational complexity
Permutation
Polynomials
Strings
Maximise
Exact Algorithms
Polynomial-time Algorithm
Count
NP-complete problem
Range of data

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Gotthilf, Z., Lewenstein, M., & Popa, A. (2010). On shortest common superstring and swap permutations. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 6393 LNCS, pp. 270-278). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6393 LNCS). https://doi.org/10.1007/978-3-642-16321-0_28

On shortest common superstring and swap permutations. / Gotthilf, Zvi; Lewenstein, Moshe; Popa, Alexandru.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6393 LNCS 2010. p. 270-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6393 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Gotthilf, Z, Lewenstein, M & Popa, A 2010, On shortest common superstring and swap permutations. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 6393 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6393 LNCS, pp. 270-278, 17th International Symposium on String Processing and Information Retrieval, SPIRE 2010, Los Cabos, Mexico, 10/11/10. https://doi.org/10.1007/978-3-642-16321-0_28
Gotthilf Z, Lewenstein M, Popa A. On shortest common superstring and swap permutations. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6393 LNCS. 2010. p. 270-278. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-16321-0_28
Gotthilf, Zvi ; Lewenstein, Moshe ; Popa, Alexandru. / On shortest common superstring and swap permutations. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6393 LNCS 2010. pp. 270-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{2417c8dfafc549c2bcc634efda8a0119,
title = "On shortest common superstring and swap permutations",
abstract = "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.",
author = "Zvi Gotthilf and Moshe Lewenstein and Alexandru Popa",
year = "2010",
doi = "10.1007/978-3-642-16321-0_28",
language = "English",
isbn = "3642163203",
volume = "6393 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "270--278",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - GEN

T1 - On shortest common superstring and swap permutations

AU - Gotthilf, Zvi

AU - Lewenstein, Moshe

AU - Popa, Alexandru

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

SN - 3642163203

SN - 9783642163203

VL - 6393 LNCS

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

SP - 270

EP - 278

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

ER -