On the generalized constrained longest common subsequence problems

DOI10.1007/s10878-009-9262-5zbMath1319.68263OpenAlexW2061395657MaRDI QIDQ491203

Yi-Ching Chen, Kun-Mao Chao

Publication date: 24 August 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9262-5

zbMATH Keywords

algorithmsdynamic programminglongest common subsequence

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Dynamic programming (90C39) Algorithms on strings (68W32)

Related Items

LCS\(k\): a refined similarity measure ⋮ The substring inclusion constraint longest common subsequence problem can be solved in quadratic time ⋮ A multiobjective optimization algorithm for the weighted LCS ⋮ Computing the longest common almost-increasing subsequence ⋮ Solving longest common subsequence problems via a transformation to the maximum clique problem ⋮ Space-efficient STR-IC-LCS computation ⋮ Fast algorithms for computing the constrained LCS of run-length encoded strings ⋮ Quadratic-time algorithm for a string constrained LCS problem ⋮ Doubly-constrained LCS and hybrid-constrained LCS problems revisited ⋮ Approximability of constrained LCS ⋮ A dynamic programming solution to a generalized LCS problem ⋮ An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints ⋮ An \(A^\ast\) search algorithm for the constrained longest common subsequence problem ⋮ Faster STR-EC-LCS Computation ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint ⋮ Constrained sequence analysis algorithms in computational biology ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Unnamed Item ⋮ Maximal common subsequence algorithms ⋮ Maximal Common Subsequence Algorithms ⋮ A data structure for substring-substring LCS length queries ⋮ A space efficient algorithm for the longest common subsequence in \(k\)-length substrings

Cites Work

• Unnamed Item
• Sequence comparison. Theory and methods
• New efficient algorithms for the LCS and constrained LCS problems
• The constrained longest common subsequence problem
• The longest common subsequence problem revisited
• A faster algorithm computing string edit distances
• Preserving order in a forest in less than logarithmic time and linear space
• A simple algorithm for the constrained sequence problems
• Constrained LCS: Hardness and Approximation
• Exemplar Longest Common Subsequence
• A linear space algorithm for computing maximal common subsequences
• Bounds on the Complexity of the Longest Common Subsequence Problem
• A fast algorithm for computing longest common subsequences
• Design and implementation of an efficient priority queue
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms for the Longest Common Subsequence Problem
• Algorithms on Strings, Trees and Sequences
• The String-to-String Correction Problem
• A New Efficient Algorithm for Computing the Longest Common Subsequence
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS