Name
Abstract | ||
|---|---|---|
Minimum Common String Partition (MCSP) has drawn a lot of attention due to its application in genome rearrangement. The best approximation algorithm has a factor O(log n log* n) and it was shown most recently that it is FPT (but with a very high running time). In this paper, we consider the decision version of the one-sided MCSP problem (formally called the exact block cover problem); namely, when one sequence is already partitioned into k blocks, how to decide whether the other sequence can be partitioned accordingly. While this decision problem is obviously in FPT, we show interesting results in this paper: (1) If each letter is allowed to appear at most twice (or three times), then the problem is polynomially solvable, (2) There is an FPT algorithm which runs in O*(2(k)) time, improving the trivial bound of O*(k!), and (3) If vertical bar Sigma vertical bar = c, c being a constant at least 2, then the problem is NP-complete. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-07956-1_2 | ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2014 |
Field | DocType | Volume |
Edit distance,Dynamic programming,Approximation algorithm,Combinatorics,Decision problem,Edge cover,Computer science,Bipartite graph,Genome rearrangement,Partition (number theory) | Conference | 8546 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.59 |
References | Authors | |
9 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haitao Jiang | 1 | 40 | 7.94 |
| Bing Su | 2 | 17 | 4.72 |
| Mingyu Xiao | 3 | 161 | 24.70 |
| Yinfeng Xu | 4 | 1636 | 108.18 |
| Farong Zhong | 5 | 46 | 11.94 |
| Binhai Zhu | 6 | 903 | 109.96 |