Approximability of constrained LCS

DOI10.1016/j.jcss.2011.10.002zbMath1244.68036MaRDI QIDQ439929

Ming-Hui Jiang

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

zbMATH Keywords

computational complexity; computational biology; approximation algorithms; longest common subsequence

Mathematics Subject Classification ID

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