咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Parameterized tractability of ... 收藏

Parameterized tractability of the maximum-duo preservation string mapping problem

印射问题的最大二部曲的保藏绳的 Parameterized 驯良

作     者: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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分