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 publicationString Processing and Information Retrieval - 17th International Symposium, SPIRE 2010, Proceedings
Pages270-278
Number of pages9
DOIs
Publication statusPublished - Nov 24 2010
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)0302-9743
ISSN (Electronic)1611-3349

Other

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

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Gotthilf, Z., Lewenstein, M., & Popa, A. (2010). On shortest common superstring and swap permutations. In String Processing and Information Retrieval - 17th International Symposium, SPIRE 2010, Proceedings (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