Approximability of constrained LCS
From MaRDI portal
Publication:439929
DOI10.1016/j.jcss.2011.10.002zbMath1244.68036MaRDI QIDQ439929
Publication date: 17 August 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.10.002
computational complexity; computational biology; approximation algorithms; longest common subsequence
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
68W20: Randomized algorithms
68W32: Algorithms on strings
Cites Work
- Unnamed Item
- Variants of constrained longest common subsequence
- On the generalized constrained longest common subsequence problems
- Combined super-/substring and super-/subsequence problems
- On finding minimal, maximal, and consistent sequences over a binary alphabet
- New efficient algorithms for the LCS and constrained LCS problems
- The constrained longest common subsequence problem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- A simple algorithm for the constrained sequence problems
- Constrained LCS: Hardness and Approximation
- The Complexity of Some Problems on Subsequences and Supersequences
- On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
- ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS