Name
Abstract | ||
|---|---|---|
The shortest common superstring and the shortest common supersequence are two well studied problems having a wide range of applications. In this paper we consider both problems with resource constraints, denoted as the Restricted Common Superstring (shortly RCSstr) problem and the Restricted Common Supersequence (shortly RCSseq). In the RCSstr (RCSseq) problem we are given a set S of n strings, s1, s2, ..., sn, and a multiset t = {t1, t2, ..., tm}, and the goal is to find a permutation π : {1,..., m} → {1, ..., m} to maximize the number of strings in S that are substrings (subsequences) of π(t) = tπ(1) tπ(2) ... tπ(m) (we call this ordering of the multiset, π(t), a permutation of t). We first show that in its most general setting the RC-Sstr problem is NP-complete and hard to approximate within a factor of n1-ε, for any ε 0, unless P = NP. Afterwards, we present two separate reductions to show that the RCSstr problem remains NP-Hard even in the case where the elements of t are drawn from a binary alphabet or for the case where all input strings are of length two. We then present some approximation results for several variants of the RCSstr problem. In the second part of this paper, we turn to the RCSseq problem, where we present some hardness results, tight lower bounds and approximation algorithms. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-21458-5_39 | CPM |
Keywords | Field | DocType |
shortest common superstring,approximation result,rcsstr problem,binary alphabet,rcsseq problem,rc-sstr problem,shortest common supersequence,restricted common superstring,restricted common supersequence,approximation algorithm,data structure,lower bound | Superstring theory,Approximation algorithm,Discrete mathematics,Substring,Combinatorics,Multiset,Permutation,Travelling salesman problem,Mathematics,Binary number,Alphabet | Conference |
Volume | ISSN | Citations |
6661 | 0302-9743 | 7 |
PageRank | References | Authors |
0.49 | 22 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Zvi Gotthilf | 2 | 68 | 5.32 |
| Moshe Lewenstein | 3 | 1214 | 76.97 |
| Alexandru Popa | 4 | 70 | 13.34 |