Tree Edit Distance and Maximum Agreement Subtree
For any derivative of Tai tree edit distance metric, we define a MAST-like problem. Computing distancess for the metric is equivalent to solving the MAST-like problem. Introduce the MAAST problem, which is equivalent to the Lu* distance in this sense. MAAST is a flexible version of MAST, which does not require exact match of labels. The complexities of MAAST are O(n2log?d) O ( n 2 log ? d ) (unordered) and O(n2) O ( n 2 ) (ordered).
tree edit distance maximum agreement subtree graph algorithms pattern recognition