Performance analysis of some simple heuristics for computing longest common subsequences

DOI10.1007/BF01185429MaRDI QIDQ1336959zbMATH OpenFDO

Authors F. Chin, Chung Keung Poon

Publication date 27 August 1995

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

longest common subsequencescan algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• The longest common subsequence problem revisited
• A large neighborhood search heuristic for the longest common subsequence problem
• New algorithms for the LCS problem
• Publication:4862293
• Algorithms for Computing Variants of the Longest Common Subsequence Problem

Cites work

• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• A longest common subsequence algorithm suitable for similar text strings
• Algorithms for approximate string matching
• Algorithms for the Longest Common Subsequence Problem
• An \(O(ND)\) difference algorithm and its variations
• An information-theoretic lower bound for the longest common subsequence problem
• Bounds on the Complexity of the Longest Common Subsequence Problem
• The String-to-String Correction Problem
• The longest common subsequence problem revisited

Cited in

(10)

• APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Analysis of evolutionary algorithms for the longest common subsequence problem
• Beam search for the longest common subsequence problem
• A hyper-heuristic for the longest common subsequence problem
• Fast Algorithms for Local Similarity Queries in Two Sequences
• A large neighborhood search heuristic for the longest common subsequence problem
• Towards hardness of approximation for polynomial time problems
• An improved algorithm for the longest common subsequence problem
• Deposition and extension approach to find longest common subsequence for thousands of long sequences

This page was built for publication: Performance analysis of some simple heuristics for computing longest common subsequences

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