Constrained LCS: Hardness and Approximation

DOI10.1007/978-3-540-69068-9_24MaRDI QIDQ3506958zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Approximability of constrained LCS
• Approximability of constrained LCS
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• The constrained longest common subsequence problem
• New efficient algorithms for the LCS and constrained LCS problems

Cites work

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

Cited in

(23)

• Difficult configurations -- on the complexity of LTrL
• Comparing incomplete sequences via longest common subsequence
• Anytime algorithms for the longest common palindromic subsequence problem
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• On solving a generalized constrained longest common subsequence problem
• Hardness of longest common subsequence for sequences with bounded run-lengths
• Approximability of constrained LCS
• Exemplar Longest Common Subsequence
• LCS Approximation via Embedding into Local Non-repetitive Strings
• Variants of constrained longest common subsequence
• Approximability of constrained LCS
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• On the generalized constrained longest common subsequence problems
• Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
• Tight conditional lower bounds for longest common increasing subsequence
• Approximating LCS in Linear Time: Beating the √n Barrier
• Constrained sequence analysis algorithms in computational biology
• Subsequence Packing: Complexity, Approximation, and Application
• Combinatorial Pattern Matching
• Algorithms and hardness for the longest common subsequence of three strings and related problems
• String editing under pattern constraints
• On the longest common rigid subsequence problem
• Longest common subsequence problem for unoriented and cyclic strings

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3506958)