标题:Minimum Common String Partition Revisited
作者:Jiang, Haitao; Zhu, Binhai; Zhu, Daming; Zhu, Hong
通讯作者:Jiang, H
作者机构:[Jiang, Haitao; Zhu, Binhai] Montana State Univ, Dept Comp Sci, Bozeman, MT 59717 USA.; [Jiang, Haitao; Zhu, Daming] Shandong Univ, Sch Comp Sci & T 更多
会议名称:4th International Frontiers of Algorithmics Workshop
会议日期:AUG 11-13, 2010
来源:FRONTIERS IN ALGORITHMICS
出版年:2010
卷:6213
页码:45-52
DOI:10.1007/978-3-642-14553-7_7
摘要:Minimum Common String Partition MCSP) has drawn much attention due to its application in genome rearrangement. In this paper, we investigate three variants of MCSP: MCSPc, which requires that there are at most c symbols in the alphabet; d-MCSP, which requires the occurrence of each symbol to be bounded by d; and x-balance MCSP, which requires the length of blocks not being x away from the average length. We show that MCSPc is NP-hard when c >= 2. As for d-MCSP, we present an FPT algorithm which runs in O* ((d!)(k)) time. As it is still unknown whether an FPT algorithm only parameterized on k exists for the general case of MCSP, we also devise an FPT algorithm for the special case x-balance MCSP parameterized on both k and x.
收录类别:CPCI-S;EI;SCOPUS
WOS核心被引频次:6
Scopus被引频次:7
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-77955901692&doi=10.1007%2f978-3-642-14553-7_7&partnerID=40&md5=963cd2a11cb7c31b50599327dd27b8e3
TOP