A lower bound for the edit-distance problem under an arbitrary cost function
From MaRDI portal
DOI10.1016/0020-0190(88)90220-7zbMATH Open0652.68090OpenAlexW1986124289MaRDI QIDQ1107330FDOQ1107330
Authors: 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Cites Work
- The String-to-String Correction Problem
- A faster algorithm computing string edit distances
- A fast algorithm for computing longest common subsequences
- An information-theoretic lower bound for the longest common subsequence problem
- Bounds for the String Editing Problem
- Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
- Algorithms for the Longest Common Subsequence Problem
- Bounds on the Complexity of the Longest Common Subsequence Problem
- On the Optimality of Some Set Algorithms
Cited In (7)
- Constrained string editing
- Lower bounding edit distances between permutations
- String editing under a combination of constraints
- Dynamic edit distance table under a general weighted cost function
- Classes of cost functions for string edit distance
- Bounds and estimates on the average edit distance
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
This page was built for publication: A lower bound for the edit-distance problem under an arbitrary cost function
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107330)
