Beam search for the longest common subsequence problem

DOI10.1016/J.COR.2009.02.005zbMath1175.90208OpenAlexW2071241868MaRDI QIDQ833536

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

beam searchlongest common subsequence problem

Mathematics Subject Classification ID

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

Related Items (12)

Deposition and extension approach to find longest common subsequence for thousands of long sequences ⋮ Solving longest common subsequence problems via a transformation to the maximum clique problem ⋮ Fast algorithms for computing the constrained LCS of run-length encoded strings ⋮ A hyper-heuristic for the longest common subsequence problem ⋮ An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints ⋮ An \(A^\ast\) search algorithm for the constrained longest common subsequence problem ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ Constrained sequence analysis algorithms in computational biology ⋮ An improved algorithm for the longest common subsequence problem ⋮ On solving the assembly line worker assignment and balancing problem via beam search ⋮ Anytime algorithms for the longest common palindromic subsequence problem ⋮ A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing a longest common subsequence for a set of strings
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• A large neighborhood search heuristic for the longest common subsequence problem
• Performance analysis of some simple heuristics for computing longest common subsequences
• Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach
• Job shop scheduling with beam search
• The Complexity of Some Problems on Subsequences and Supersequences
• A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
• Algorithms on Strings, Trees and Sequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Probabilistic Beam Search for the Longest Common Subsequence Problem
• Improved lower bounds for the early/tardy scheduling problem with no idle time

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