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

DOI10.1007/S10878-012-9588-2zbMATH Open1314.90066OpenAlexW2168333158MaRDI QIDQ489728FDOQ489728

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

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

zbMATH Keywords

finite automatalongest common subsequenceNP-harddesign of algorithmsconstrained LCS

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

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

Cited In (3)

• Tight conditional lower bounds for longest common increasing subsequence
• Linear-space S-table algorithms for the longest common subsequence problem
• Title not available (Why is that?)

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)