Performance analysis of some simple heuristics for computing longest common subsequences

DOI10.1007/BF01185429zbMath0820.68050MaRDI QIDQ1336959

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)

Related Items

Deposition and extension approach to find longest common subsequence for thousands of long sequences, Beam search for the longest common subsequence problem, Fast Algorithms for Local Similarity Queries in Two Sequences, A hyper-heuristic for the longest common subsequence problem, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, A large neighborhood search heuristic for the longest common subsequence problem, An improved algorithm for the longest common subsequence problem, Unnamed Item, APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †

Cites Work

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