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

DOI10.1007/S10878-012-9588-2MaRDI QIDQ489728zbMATH OpenOpenAlexFDO

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

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

finite automatalongest common subsequenceNP-harddesign of algorithmsconstrained LCS

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Faster STR-EC-LCS computation
• A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
• A dynamic programming solution to a generalized LCS problem
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• The constrained longest common subsequence problem

Cites work

• scientific article; zbMATH DE number 6697960 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• A fast algorithm for computing longest common subsequences
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• A new efficient algorithm for computing the longest common subsequence
• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Algorithms for the Longest Common Subsequence Problem
• Algorithms for two versions of LCS problem for indeterminate strings
• An algorithm and applications to sequence alignment with weighted constraints
• Beam search for the longest common subsequence problem
• Bit-parallel algorithm for the constrained longest common subsequence problem
• Constrained LCS: Hardness and Approximation
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Efficient algorithms for the block edit problems
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• Efficient string matching
• Fast Pattern Matching in Strings
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• Finite automata based algorithms on subsequences and supersequences of degenerate strings
• New efficient algorithms for the LCS and constrained LCS problems
• On the generalized constrained longest common subsequence problems
• Quadratic-time algorithm for a string constrained LCS problem
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem
• The constrained longest common subsequence problem
• The longest common subsequence problem revisited

Cited in

(7)

• Tight conditional lower bounds for longest common increasing subsequence
• Tight conditional lower bounds for longest common increasing subsequence
• The generalized constrained longest common subsequence in the run-length encoded format
• A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
• Linear-space S-table algorithms for the longest common subsequence problem
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• Faster STR-EC-LCS computation

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

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