Approximability of constrained LCS

DOI10.1016/j.jcss.2011.10.002zbMath1244.68036OpenAlexW2001332692MaRDI 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 complexitycomputational biologyapproximation algorithmslongest common subsequence

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20) Algorithms on strings (68W32)

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

This page was built for publication: Approximability of constrained LCS