Name
Abstract | ||
|---|---|---|
In this paper we investigate the parameterized complexity of the Maximum-Duo Preservation String Mapping Problem, the complementary of the Minimum Common String Partition Problem. We show that this problem is fixed-parameter tractable when parameterized by the number k of conserved duos, by first giving a parameterized algorithm based on the color-coding technique and then presenting a reduction to a kernel of size O ( k 6 ) . |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2016.07.011 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Computational biology,Common string partition,Parameterized algorithms,Kernelization | Journal | abs/1512.03220 |
Issue | ISSN | Citations |
C | 0304-3975 | 1 |
PageRank | References | Authors |
0.37 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefano Beretta | 1 | 27 | 9.68 |
| Mauro Castelli | 2 | 595 | 56.31 |
| Riccardo Dondi | 3 | 89 | 18.42 |