标题:Exponential and Polynomial Time Algorithms for the Minimum Common String Partition Problem
作者:Fu, Bin; Jiang, Haitao; Yang, Boting; Zhu, Binhai
通讯作者:Fu, B
作者机构:[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
出版年:2011
卷:6831
页码:299-310
DOI:10.1007/978-3-642-22616-8_24
摘要: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.
收录类别:CPCI-S;EI;SCOPUS
WOS核心被引频次:4
Scopus被引频次:7
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-80052005802&doi=10.1007%2f978-3-642-22616-8_24&partnerID=40&md5=cb4542c7f88d13171f2960c55c47badc
TOP