A large neighborhood search heuristic for the longest common subsequence problem

DOI10.1007/S10732-007-9038-YzbMATH Open1211.90302OpenAlexW1981915844MaRDI QIDQ953288FDOQ953288

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

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

zbMATH Keywords

dynamic programmingheuristiclongest common subsequencelarge neighborhood search

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• A policy-based learning beam search for combinatorial optimization
• A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• Resequencing a set of strings based on a target string
• Beam search for the longest common subsequence problem
• Probabilistic Beam Search for the Longest Common Subsequence Problem
• A hyper-heuristic 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
• Beam-ACO for the repetition-free longest common subsequence problem
• Deposition and extension approach to find longest common subsequence for thousands of long sequences

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)