TY - JOUR
T1 - Parameterized tractability of the maximum-duo preservation string mapping problem
AU - Beretta, Stefano
AU - Castelli, Mauro
AU - Dondi, Riccardo
N1 - Beretta, S., Castelli, M., & Dondi, R. (2016). Parameterized tractability of the maximum-duo preservation string mapping problem. Theoretical Computer Science, 646, 16-25. https://doi.org/10.1016/j.tcs.2016.07.011
PY - 2016
Y1 - 2016
N2 - 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(k6).
AB - 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(k6).
KW - Common string partition
KW - Computational biology
KW - Kernelization
KW - Parameterized algorithms
UR - http://www.scopus.com/inward/record.url?scp=84997228970&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2016.07.011
DO - 10.1016/j.tcs.2016.07.011
M3 - Article
AN - SCOPUS:84997228970
VL - 646
SP - 16
EP - 25
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -