TY - RPRT
T1 - Ordered Tree Edit Distance with Merge and Split Operations
AU - Bille, Philip
PY - 2003/9
Y1 - 2003/9
N2 - Comparing trees is a fundamental problem in computer science. In particular, the ordered tree edit distance problem, defined as the problem of comparing ordered and labeled trees based on the cost and number of edit operations needed to transform a tree T1 into another tree T2 , arise in many applications. For the simple edit operations of inserting, deleting and relabeling a node the problem is a well-studied problem and algorithms with o(n 4 ) time complexity exists. In this paper we extend the set of operations with merge and split operations. We argue that this new problem naturally generalize the old problem and we provide polynomial time algorithms for solving it.
AB - Comparing trees is a fundamental problem in computer science. In particular, the ordered tree edit distance problem, defined as the problem of comparing ordered and labeled trees based on the cost and number of edit operations needed to transform a tree T1 into another tree T2 , arise in many applications. For the simple edit operations of inserting, deleting and relabeling a node the problem is a well-studied problem and algorithms with o(n 4 ) time complexity exists. In this paper we extend the set of operations with merge and split operations. We argue that this new problem naturally generalize the old problem and we provide polynomial time algorithms for solving it.
KW - tree edit distance
KW - ordered trees
KW - polynomial time algorithms
KW - merge and split operations
KW - node editing operations
M3 - Report
T3 - IT University Technical Report Series
BT - Ordered Tree Edit Distance with Merge and Split Operations
PB - IT-Universitetet i København
CY - Copenhagen
ER -