A large neighborhood search heuristic for the longest common subsequence problem

DOI10.1007/S10732-007-9038-YMaRDI QIDQ953288zbMATH OpenOpenAlexFDO

Authors T. Easton, Abhilash Singireddy

Publication date 17 November 2008

Published in Journal of Heuristics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10732-007-9038-y

zbMATH Keywords

dynamic programmingheuristiclongest common subsequencelarge neighborhood search

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39)

Recommendations

• A specialized branching and fathoming technique for the longest common subsequence problem
• Performance analysis of some simple heuristics for computing longest common subsequences
• Algorithms for the longest common subsequence problem for multiple strings based on geometric maxima
• An improved algorithm for the longest common subsequence problem
• Beam search for the longest common subsequence problem

Cites work

• scientific article; zbMATH DE number 4174365 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 1516705 (Why is no real title available?)
• scientific article; zbMATH DE number 194738 (Why is no real title available?)
• scientific article; zbMATH DE number 3325181 (Why is no real title available?)
• A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
• A fast algorithm for computing longest common subsequences
• A linear space algorithm for computing maximal common subsequences
• A survey of very large-scale neighborhood search techniques
• Algorithms for the Longest Common Subsequence Problem
• An Automatic Method of Solving Discrete Programming Problems
• Computing a longest common subsequence for a set of strings
• On finding minimal length superstrings
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Performance analysis of some simple heuristics for computing longest common subsequences
• Sparse dynamic programming II
• The Complexity of Some Problems on Subsequences and Supersequences
• The string merging problem

Cited in

(14)

• A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem
• A policy-based learning beam search for combinatorial optimization
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• Beam search for the longest common subsequence problem
• Resequencing a set of strings based on a target string
• A hyper-heuristic for the longest common subsequence problem
• Probabilistic Beam Search for the Longest Common Subsequence Problem
• A Largest Common d-Dimensional Subsequence of Two d-Dimensional Strings
• Performance analysis of some simple heuristics for computing longest common subsequences
• Anytime algorithms for the longest common palindromic subsequence problem
• A specialized branching and fathoming technique for the longest common subsequence problem
• An improved algorithm for the longest common subsequence problem
• Deposition and extension approach to find longest common subsequence for thousands of long sequences
• Beam-ACO for the repetition-free longest common subsequence problem

Describes a project that uses

Uses Software

• ClustalW

This page was built for publication: A large neighborhood search heuristic 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 Q953288)