CODEWITHSUNDEEP
branch-and-bound
Dark Star
Dark Star

Reputation: 43

Branch and Bound approach to the edit distance algorithm

I am trying to implement Branch and Bound approach to the edit distance algorithm. I can't find any hints over internet to start with. Can anyone help me to get into the track of the algorithm.

Upvotes: 1

Views: 280

Answers (1)

dfrib
dfrib

Reputation: 73186

My apologies for posting this as an answer, I wanted to add it as just a comment, but I don't have sufficient reputation to add comments.

Try to approach your literature search of this subject rather in the context of the graph similarity problem than for the edit distance algorithm; the prior is a more general and well-studied problem which the problem of finding the minimum edit distance fall under. The strings in any instance of your edit distance problem can be described as simple directional graphs, and the operations of insertion/deletion and substitution in the edit distance algorithm has similar operations in the graph similarity problem (e.g., insertion of vertices and edges/deletion of vertices and edges/changing labels on edges and so on).

Upvotes: 1

Related Questions