A lower bound for the edit-distance problem under an arbitrary cost function

DOI10.1016/0020-0190(88)90220-7zbMath0652.68090OpenAlexW1986124289MaRDI QIDQ1107330

Xiaoqiu Huang

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90220-7

zbMATH Keywords

lower boundedit distancelongest common subsequencesRAM model of computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cites Work

• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• A faster algorithm computing string edit distances
• An information-theoretic lower bound for the longest common subsequence problem
• Bounds for the String Editing Problem
• 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
• On the Optimality of Some Set Algorithms

This page was built for publication: A lower bound for the edit-distance problem under an arbitrary cost function