Beam search for the longest common subsequence problem

DOI10.1016/J.COR.2009.02.005MaRDI QIDQ833536zbMATHOpenAlexFDO

Authors Christian Blum, Maria J. Blesa, Manuel López-Ibáñez

Publication date 14 August 2009

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2117/86874

zbMATH Keywords

longest common subsequence problembeam search

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Search theory (90B40)

Recommendations

• Probabilistic Beam Search for the Longest Common Subsequence Problem
• An improved algorithm for the longest common subsequence problem
• Beam-ACO for the repetition-free longest common subsequence problem
• On solving a generalized constrained longest common subsequence problem
• A beam search for the shortest common supersequence problem guided by an approximate expected length calculation

Cites work

• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
• A large neighborhood search heuristic for the longest common subsequence problem
• A specialized branching and fathoming technique for the longest common subsequence problem
• Algorithms on Strings, Trees and Sequences
• Ant colony optimization.
• Computing a longest common subsequence for a set of strings
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• Improved lower bounds for the early/tardy scheduling problem with no idle time
• Job shop scheduling with beam search
• Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Performance analysis of some simple heuristics for computing longest common subsequences
• Probabilistic Beam Search for the Longest Common Subsequence Problem
• The Complexity of Some Problems on Subsequences and Supersequences

Cited in

(18)

• A large neighborhood search heuristic for the longest common subsequence problem
• Incremental beam search
• An improved algorithm for the longest common subsequence problem
• A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Probabilistic Beam Search for the Longest Common Subsequence Problem
• A hyper-heuristic for the longest common subsequence problem
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• On solving the assembly line worker assignment and balancing problem via beam search
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• Beam-ACO for the repetition-free longest common subsequence problem
• An \(A^\ast\) search algorithm for the constrained longest common subsequence problem
• A beam search for the shortest common supersequence problem guided by an approximate expected length calculation
• A neural network based guidance for a BRKGA: an application to the longest common square subsequence problem
• Anytime algorithms for the longest common palindromic subsequence problem
• Constrained sequence analysis algorithms in computational biology
• Deposition and extension approach to find longest common subsequence for thousands of long sequences

This page was built for publication: Beam search for the longest common subsequence problem

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