A survey on tree edit distance and related problems (Q557823)

The paper deals with matching problems based on simple primitive operations applied to labeled trees. Particularly, tree edit distance problem, tree alignment distance problem and tree inclusion problem are surveyed. In order to do that, problems and algorithms are presented in a common framework. For each problem and its variations both ordered and unordered versions are reviewed. Also central algorithms for each of the poblems are presented in more detail, including proof of correctness and time complexity analysis. The paper concludes with a summary of results in table form and a short list of possible topics for further research.