标题：Minimum Common String Partition Revisited
作者：Jiang, Haitao; Zhu, Binhai; Zhu, Daming; Zhu, Hong
作者机构：[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
摘要：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.