An efficient bottom-up distance between trees
Gabriel Valiente · 2005
A new bottom-up distance measure for labeled trees, which is based on the largest common forest of the trees and has the threefold advantage of independence of particular edit costs, low complexity, and coverage of ordered and unordered trees, is introduced and related in this paper with other distance measures published in the literature. Algorithms for computing the bottom-up distance in time linear in the number of nodes are given in full detail. Key words design and analysis of algorithms, combinatorial problems, graph algorithms, pattern matching, tree pattern matching, tree isomorphism, subtree isomorphism, edit distance, metric space, largest common forest 1