Constrained LCS: Hardness and Approximation

DOI10.1007/978-3-540-69068-9_24zbMath1143.68637OpenAlexW1848152589MaRDI QIDQ3506958

Zvi Gotthilf, Danny Hermelin, Moshe Lewenstein

Publication date: 17 June 2008

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69068-9_24

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (9)

Variants of constrained longest common subsequence ⋮ Approximability of constrained LCS ⋮ An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ On the generalized constrained longest common subsequence problems ⋮ Constrained sequence analysis algorithms in computational biology ⋮ Unnamed Item ⋮ Comparing incomplete sequences via longest common subsequence ⋮ Anytime algorithms for the longest common palindromic subsequence problem

Cites Work

• The constrained longest common subsequence problem
• A faster algorithm computing string edit distances
• A simple algorithm for the constrained sequence problems
• A linear space algorithm for computing maximal common subsequences
• Bounds on the Complexity of the Longest Common Subsequence Problem
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms for the Longest Common Subsequence Problem
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS

This page was built for publication: Constrained LCS: Hardness and Approximation