标题：Exponential and Polynomial Time Algorithms for the Minimum Common String Partition Problem
作者：Fu, Bin; Jiang, Haitao; Yang, Boting; Zhu, Binhai
作者机构：[Fu, Bin] Univ Texas Pan Amer, Dept Comp Sci, Edinburg, TX 78539 USA.; [Jiang, Haitao] Shandong Univ, Sch Comp Sci, Jinan 250100, Shandong, Peoples 更多
会议名称：5th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2011)
会议日期：AUG 04-06, 2011
来源：COMBINATORIAL OPTIMIZATION AND APPLICATIONS
摘要：Given two strings S and S' of the same length, the Minimum Common String Partition (MCSP) is to partition them into the minimum number of strings S = S-1 . S-2 ... S-k and S' = S'(1) . S'(2) ... S'(k) such that the substrings < S'(1), S'(2), ... , S'(k)> is a permutation of < S-1, S-2, ... , S-k >. MCSP is an NP-complete problem originating from computational genomics. There exists constant-factor approximations for some special cases, but the factors are impractical. On exact; solutions, it is open whether there exists an FPT algorithm for the general case and some inefficient FPT algorithms for very special cases. In this paper, we present an O(2(n)n(O(1))) time algorithm for the general case. We also show an O(n(log n)(2)) time algorithm which solves the case for almost all strings S and S' if the length of each block in their minimum common partition is at least d(0) log n/log t for some positive constant d(0), where t is the size of the alphabet Sigma.