Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion

DOI10.1007/s10878-012-9588-2zbMath1314.90066OpenAlexW2168333158MaRDI QIDQ489728

Chiou-Ting Tseng, Chang-Biau Yang, Hsing-Yen Ann

Publication date: 21 January 2015

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

Full work available at URL: https://doi.org/10.1007/s10878-012-9588-2

zbMATH Keywords

design of algorithmsNP-hardfinite automatalongest common subsequenceconstrained LCS

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (3)

Linear-space S-table algorithms for the longest common subsequence problem ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Quadratic-time algorithm for a string constrained LCS problem
• On the generalized constrained longest common subsequence problems
• A new efficient algorithm for computing the longest common subsequence
• Beam search for the longest common subsequence problem
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• New efficient algorithms for the LCS and constrained LCS problems
• Efficient algorithms for the block edit problems
• Finite automata based algorithms on subsequences and supersequences of degenerate strings
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• The constrained longest common subsequence problem
• The longest common subsequence problem revisited
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• A simple algorithm for the constrained sequence problems
• Constrained LCS: Hardness and Approximation
• Efficient string matching
• A fast algorithm for computing longest common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Fast Pattern Matching in Strings
• Algorithms for the Longest Common Subsequence Problem
• Dynamic Perfect Hashing: Upper and Lower Bounds
• The String-to-String Correction Problem
• Bit-Parallel Algorithm for the Constrained Longest Common Subsequence Problem
• AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS

This page was built for publication: Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion