Parameterized tractability of the maximum-duo preservation string mapping problem

作     者：Beretta, Stefano Castelli, Mauro Dondi, Riccardo 

作者机构：CNR Ist Tecnol Biomed Segrate Italy Univ Milano Bicocca Dipartimento Informat Sistemist & Comunicaz Milan Italy Univ Nova Lisboa NOVA IMS Lisbon Portugal Univ Bergamo Dipartimento Lettere Filosofia & Comunicaz Bergamo Italy 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2016年第646卷第0期

页      面：16-25页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Computational biology Common string partition Parameterized algorithms Kernelization 

摘      要：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.