An A^ search algorithm for the constrained longest common subsequence problem

DOI10.1016/J.IPL.2020.106041MaRDI QIDQ2224853zbMATH OpenOpenAlexFDO

Authors Marko Djukanovic, Christoph Berger, Günther R. Raidl, Christian Blum

Publication date 4 February 2021

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2020.106041

zbMATH Keywords

\(A^\ast\) searchcombinatorial problemsconstrained sequenceslongest common subsequences

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Algorithms on strings (68W32)

Recommendations

• A fast algorithm of constrained longest common subsequence
• scientific article; zbMATH DE number 6697960
• On solving a generalized constrained longest common subsequence problem
• Bit-parallel algorithm for the constrained longest common subsequence problem
• A simple algorithm for the constrained sequence problems

Cites work

• A fast algorithm for computing longest common subsequences
• A longest common subsequence algorithm suitable for similar text strings
• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Beam search for the longest common subsequence problem
• Computing a longest common palindromic subsequence
• Faster algorithms for computing longest common increasing subsequences
• scientific article; zbMATH DE number 1615278 (Why is no real title available?)
• scientific article; zbMATH DE number 6697960 (Why is no real title available?)
• New efficient algorithms for the LCS and constrained LCS problems
• On the generalized constrained longest common subsequence problems
• Preserving order in a forest in less than logarithmic time and linear space
• Repetition-free longest common subsequence
• Sequence comparison. Theory and methods
• The Complexity of Some Problems on Subsequences and Supersequences
• The constrained longest common subsequence problem

Cited in

(7)

• An approximate \(A^{\ast}\) algorithm and its application to the SCS problem.
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• On solving a generalized constrained longest common subsequence problem
• scientific article; zbMATH DE number 6697960 (Why is no real title available?)
• A fast algorithm of constrained longest common subsequence
• A multiobjective optimization algorithm for the weighted LCS
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization

This page was built for publication: An \(A^\ast\) search algorithm for the constrained longest common subsequence problem

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