版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.