The Computational Hardness of Estimating Edit Distance.

Alexandr Andoni Robert Krauthgamer

Published in: SIAM J. Comput. (2010)

Keyphrases

edit distance
distance measure
approximate string matching
edit operations
graph matching
similarity measure
string matching

string edit distance
approximate matching
distance function
string similarity
graph edit distance
levenshtein distance
longest common subsequence

tree structured data
dynamic programming
computational complexity
dissimilarity measure
tree edit distance
distance computation

worst case
data sets
np hard
object recognition
pattern recognition
neural network