Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding.
Debarati DasTomasz KociumakaBarna SahaPublished in: CoRR (2021)
Keyphrases
- approximation algorithms
- edit distance
- rna secondary structures
- rna secondary structure prediction
- longest common subsequence
- np hard
- edit operations
- minimum cost
- worst case
- special case
- graph matching
- vertex cover
- levenshtein distance
- similarity measure
- string matching
- distance measure
- string similarity
- string edit distance
- approximate string matching
- approximation ratio
- dynamic time warping
- tree edit distance
- graph edit distance
- distance function
- dynamic programming
- triangle inequality
- approximate matching
- constant factor approximation
- constant factor
- pattern recognition
- pattern matching
- constraint satisfaction problems
- linear programming
- lower bound
- object recognition