Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
| Autor: | Chiou-Ting Tseng, Hsing-Yen Ann, Chang-Biau Yang |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
Control and Optimization Finite-state machine Applied Mathematics String (computer science) Substring Computer Science Applications Longest common subsequence problem Combinatorics Constraint (information theory) Computational Theory and Mathematics Theory of computation Subsequence Discrete Mathematics and Combinatorics Algorithm Time complexity Mathematics |
| Zdroj: | Journal of Combinatorial Optimization. 28:800-813 |
| ISSN: | 1573-2886 1382-6905 |
| DOI: | 10.1007/s10878-012-9588-2 |
| Popis: | In this paper, we revisit a recent variant of the longest common subsequence (LCS) problem, the string-excluding constrained LCS (STR-EC-LCS) problem, which was first addressed by Chen and Chao (J Comb Optim 21(3):383---392, 2011). Given two sequences $$X$$ and $$Y$$ of lengths $$m$$ and $$n,$$ respectively, and a constraint string $$P$$ of length $$r,$$ we are to find a common subsequence $$Z$$ of $$X$$ and $$Y$$ which excludes $$P$$ as a substring and the length of $$Z$$ is maximized. In fact, this problem cannot be correctly solved by the previously proposed algorithm. Thus, we give a correct algorithm with $$O(mnr)$$ time to solve it. Then, we revisit the STR-EC-LCS problem with multiple constraints $$\{ P_1, P_2, \ldots , P_k \}.$$ We propose a polynomial-time algorithm which runs in $$O(mnR)$$ time, where $$R = \sum _{i=1}^{k} |P_i|,$$ and thus it overthrows the previous claim of NP-hardness. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink