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-pa...
详细信息
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)). (C) 2016 Elsevier B.V. All rights reserved.
This is a corrigendum for our paper [1] , as we have found that the first FPT algorithm for the Maximum-Duo Preservation string Mapping Problem we presented is incorrect. However, we show that, by slightly modifying t...
详细信息
This is a corrigendum for our paper [1] , as we have found that the first FPT algorithm for the Maximum-Duo Preservation string Mapping Problem we presented is incorrect. However, we show that, by slightly modifying the color-coding technique on which the algorithm is based, we can fix the error, thus giving a correct FPT algorithm for Maximum-Duo Preservation string Mapping Problem.
暂无评论