A Survey on Tree Edit Distance and Related Problems
---
paper_title: Fast comparison of evolutionary trees

paper_content:

Abstract Constructing evolutionary trees for species sets is a fundamental problem in biology. Unfortunately, there is no single agreed upon method for this task, and many methods are in use. Current practice dictates that trees be constructed using different methods and that the resulting trees then be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study the Unrooted Maximum Agreement Subtree Problem ( UMAST ) and its rooted variant ( RMAST ). The UMAST problem is as follows: given a set A and two trees T 0 and T 1 leaf-labeled by the elements of A , find a maximum cardinality subset B of A such that the restrictions of T 0 and T 1 to B are topologically isomorphic. Our main result is an O ( n 2 + o (1) ) time algorithm for the UMAST problem. We also derive an O ( n 2 ) time algorithm for the RMAST problem. The previous best algorithm for both these problems has running time O ( n 4.5 + o (1) ).
---
paper_title: Simple fast algorithms for the editing distance between trees and related problems

paper_content:

Ordered labeled trees are trees in which the left-to-right order among siblings is significant. The distance between two ordered trees is considered to be the weighted number of edit operations (insert, delete, and modify) to transform one tree to another. The problem of approximate tree matching is also considered. Specifically, algorithms are designed to answer the following kinds of questions:1. What is the distance between two trees? 2. What is the minimum distance between $T_1 $ and $T_2 $ when zero or more subtrees can be removed from $T_2 $? 3. Let the pruning of a tree at node n mean removing all the descendants of node n. The analogous question for prunings as for subtrees is answered.A dynamic programming algorithm is presented to solve the three questions in sequential time $O(|T_1 | \times |T_2 | \times \min ({\textit{depth}}(T_1 ),{\textit{leaves}}(T_1 )) \times \min ({\textit{depth}}(T_2 ),{\textit{leaves}}(T_2 )))$ and space $O(|T_1 | \times |T_2 |)$ compared with $O(|T_1 | \times |T_2 | \t...
---
paper_title: A Tree-to-Tree Distance and Its Application to Cluster Analysis

paper_content:

A distance measure between two trees is proposed. Using the idea of language transformation, a tree can be derived from another by a series of transformations. The distance between the two trees is the minimum-cost sequence of transformations. Based on this definition, an algorithm that generates the distance for any two trees is presented. Cluster analysis for patterns represented by tree structures is discussed. Using a tree-to-tree distance, the similarity between patterns is measured in terms of distance between their tree representations. An illustrative example on clustering of character patterns is presented.
---
paper_title: Ordered and Unordered Tree Inclusion

paper_content:

The following tree-matching problem is considered: Given labeled trees $P$ and $T$, can $P$ be obtained from $T$ by deleting nodes? Deleting a node $u$ entails removing all edges incident to $u$ and, if $u$ has a parent $v$, replacing the edge from $v$ to $u$ by edges from $v$ to the children of $u$. The problem is motivated by the study of query languages for structured text databases. Simple solutions to this problem require exponential time. For ordered trees an algorithm is presented that requires $O(|P| |T|)$ time and space. The corresponding problem for unordered trees is also considered and a proof of its NP-completeness is given. An algorithm is presented for the unordered problem. This algorithm works in $O(|P| |T|)$ time if the out-degrees of the nodes in $P$ are bounded by a constant, and in polynomial time if they are $O(\log |T|)$.
---
paper_title: A Tree-Matching Algorithm Based on Node Splitting and Merging

paper_content:

An algorithm that computes the best matching of two trees is described. The degree of mismatch, i.e., the distance, is measured in terms of the number of node splitting and merging operations required. The proposed tree distance is a more appropriate measurement of structural defonnation than the tree distance measure in terms of the number of insertions, deletions, and substitutions of tree nodes, as defined in previous studies. An algorithm that uses a divide-and-conquer strategy is presented. The analysis shows that the time complexity is O(NM2) where N and Al are the number of nodes of the two trees, respectively. The algorithm has been implemented on a VAX 11/780.
---
paper_title: Approximate tree matching in the presence of variable length don't cares

paper_content:

Ordered labeled trees are trees in which the sibling order matters. This paper presents algorithms for three problems having to do with approximate matching for such trees with variable length don′t cares (VLDCs). In strings, a VLDC symbol in the pattern may substitute for zero or more symbols in the data string. For example, if "com∗er" is the pattern, then the "∗" would substitute for the substring "put" when matching the data string "computer." Approximate VLDC matching in strings means that after the best possible substitution, the pattern still need not be the same as the data string for a match to be allowed. For example, "com∗er" matches "counter" within distance one (representing the cost of removing the "m" from "com∗er" and having the "∗" substitute for "unt"). We generalize approximate VLDC string matching to three algorithms for approximate VLDC matching on trees. The time complexity of our algorithms is O(|P| × |D| × min(depth(P), leaves(P)) × min(depth(D), leaves(D))) (where |P| and |D| are the number of nodes respectively of the pattern P and the data tree D), the same as for the best approximate tree matching algorithm without VLDCs previously reported.
---
paper_title: Computing the edit-distance between unrooted ordered trees

paper_content:

An ordered tree is a tree in which each node's incident edges are cyclically ordered; think of the tree as being embedded in the plane. Let A and B be two ordered trees. The edit distance between A and B is the minimum cost of a sequence of operations (contract an edge, uncontract an edge, modify the label of an edge) needed to transform A into B. We give an O(n3 log n) algorithm to compute the edit distance between two ordered trees.
---
paper_title: Maximum Agreement Subtree in a Set of Evolutionary Trees-Metrics and Efficient Algorithms

paper_content:

The maximum agreement subtree approach is one method of reconciling different evolutionary trees for the same set of species. An agreement subtree enables choosing a subset of the species for whom the restricted subtree is equivalent (under a suitable definition) in all given evolutionary trees. ::: Recently, dynamic programming ideas were used to provide polynomial time algorithms for finding a maximum homeomorphic agreement subtree of two trees. Generalizing these methods to sets of more than two trees yields algorithms that are exponential in the number of trees. Unfortunately, it turns out that in reality one is usually presented with more than two trees, sometimes as many as thousands of trees. ::: In this paper we prove that the maximum homeomorphic agreement subtree problem is $\cal{NP}$-complete for three trees with unbounded degrees. We then show an approximation algorithm of time O(kn5) for choosing the species that are not in a maximum agreement subtree of a set of k trees. Our approximation is guaranteed to provide a set that is no more than 4 times the optimum solution. ::: While the set of evolutionary trees may be large in practice, the trees usually have very small degrees, typically no larger than three. We develop a new method for finding a maximum agreement subtree of k trees, of which one has degree bounded by d. This new method enables us to find a maximum agreement subtree in time O(knd + 1+ n2d).
---
paper_title: Alignment of Trees - An Alternative to Tree Edit

paper_content:

In this paper, we propose the alignment of trees as a measure of the similarity between two labeled trees. Both ordered and unordered trees are considered. An algorithm is designed for ordered trees. The time complexity of this algorithm is O(¦T1¦· s¦T2· (deg(T1) + deg(T2))2), where ¦Ti¦ is the number of nodes in T i and deg(T i ) is the degree of T i , i=1,2. The algorithm is faster than the best known algorithm for tree edit when deg(T1) and deg(T2) are smaller than the depths of T1 and T2. For unordered trees, we show that the alignment problem can be solved in polynomial time if the trees have a bounded degree and becomes NP-hard if one of the trees is allowed to have an arbitrary degree. In contrast, the edit problem for unordered trees is NP-hard even if both trees have a bounded degree [17]. Finally, multiple alignment of trees is discussed.
---
paper_title: Approximation Algorithms for the Largest Common Subtree Problem.

paper_content:

The largest common subtree problem is to find a largest subtree which occurs as a common subgraph in a given collection of trees. We show that in case of bounded degree trees, we can achieve an approximation ratio of O(( n*loglog n ) / log^{2} n). In case of unbounded degree nodes, we give an algorithm with approximation ratio O(( n*(loglog n)^{2}) / log^{2} n) when the trees are unlabeled. An approximation ratio of O(( n*(loglog n)^{2} ) / log^{2} n) is also achieved for the case of labeled unbounded degree trees provided the number of distinct labels is O(log^{O(1)} n).
---
paper_title: A tree-edit-distance algorithm for comparing simple, closed shapes

paper_content:

A b s t r a c t We discuss a graph-algorithmic approach to comparing shapes. We focus in this paper on comparing simple closed curves in the plane. Our approach is to (1) represent such a shape by its skeleton, which is a tree embedded in the plane, and (2) compare two shapes by comparing their skeletons via tree edit-distance. In this paper, we define our version of tree edit-distance (it differs from that previously described in the literature), and give a polynomial-time algorithm to compute the distance between two trees.
---
paper_title: The Tree-to-Tree Correction Problem

paper_content:

The tree-to-tree correctmn problem Is to determine, for two labeled ordered trees T and T', the distance from T to T' as measured by the mlmmum cost sequence of edit operaUons needed to transform T into T' The edit operations investigated allow changing one node of a tree into another node, deleting one node from a tree, or inserting a node into a tree An algorithm Is presented which solves this problem m time O(V* V'*LZ* L'2), where V and V' are the numbers of nodes respectively of T and T', and L and L' are the maximum depths respectively of T and T' Possible apphcatmns are to the problems of measuring the similarity between trees, automatic error recovery and correction for programming languages, and determining the largest common substructure of two trees
---
paper_title: ATreeGrep: approximate searching in unordered trees

paper_content:

An unordered labeled tree is a tree in which each node has a string label and the parent-child relationship is significant, but the order among siblings is unimportant. This paper presents an approach to the nearest neighbor search problem for these trees. Given a database D of unordered labeled trees and a query tree Q, the goal is to find those trees in D that "approximately" contain Q. Our approach is based on storing the paths of the trees in a suffix array and then counting the number of mismatching paths between the query tree and a data tree. To speed up a search, we use a hash-based technique to filter out unqualified data trees at an early stage of the search. Experimental results obtained by running our techniques on phylogenetic trees and synthetic data demonstrate the good performance of the proposed approach. We also discuss the use of our work in XML and scientific database management.
---
paper_title: Faster tree pattern matching

paper_content:

Recently, R. Kosaraju (Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, p.178-83) gave an O(nm/sup 0.75/ polylog(m))-step algorithm for tree pattern matching. The authors improve this result by designing a simple O(n square root m polylog (m)) algorithm. >
---
paper_title: On the approximation of largest common subtrees and largest common point sets

paper_content:

This paper considers the approximability of the largest common subtree and the largest common point-set problems, which have applications in molecular biology. It is shown that the problems cannot be approximated within a factor of n1−e in polynomial time for any e>0 unless NP⊆ZPP, while a general search algorithm which approximates both problems within a factor of O(n/logn) is presented. For trees of bounded degree, an improved algorithm which approximates the largest common subtree within a factor of O(n/log2n) is presented. Moreover, several variants of the largest common subtree problem are studied.
---
paper_title: Efficient tree pattern matching

paper_content:

A classic open problem on tree pattern matching is whether the naive O(mn)-step algorithm for finding all the occurrences of a pattern tree of size m in a text tree of size n can be improved. An O(nM/sup 0.75/ polylog(m))-step algorithm for this tree pattern matching problem is designed. The problems of linear string matching with don't care symbols and linear string max-min convolution are treated. >
---
paper_title: Efficient Parallel Algorithms for Tree Editing Problems

paper_content:

The tree editing problem for input trees T1 and T2 is defined as transforming T1 into T2 by performing a series of weighted edit operations on T1 with overall minimum cost. An edit operation can be the deletion, the insertion, and the substitution. Depending on the precise definition of the edit operation, there are several edit distances between trees. This paper presents a framework for solving tree editing problems in parallel. We show polylogrithmic time algorithms under this framework.
---
paper_title: Nonlinear pattern matching in trees

paper_content:

Tree pattern matching is a fundamental operation that is used in a number of programming tasks such as mechanical theorem proving, term rewriting, symbolic computation, and nonprocedural programming languages. In this paper, we present new sequential algorithms for nonlinear pattern matching in trees. Our algorithm improves upon know tree pattern matching algorithms in important aspects such as time performance, ease of integration with several reduction strategies and ability to avoid unnecessary computation steps on match attempts that fail. The expected time complexity of our algorithm is linear in the sum of the sizes of the two trees.
---
paper_title: Proof Verification and Hardness of Approximation Problems

paper_content:

The class PCP(f(n),g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that used O(f(n)) random bits, queries O(g(n)) bits of its oracle and behaves as follows: If x in L then there exists an oracle y such that the machine accepts for all random choices but if x not in L then for every oracle y the machine rejects with high probability. Arora and Safra (1992) characterized NP as PCP(log n, (loglogn)/sup O(1)/). The authors improve on their result by showing that NP=PCP(logn, 1). The result has the following consequences: (1) MAXSNP-hard problems (e.g. metric TSP, MAX-SAT, MAX-CUT) do not have polynomial time approximation schemes unless P=NP; and (2) for some epsilon >0 the size of the maximal clique in a graph cannot be approximated within a factor of n/sup epsilon / unless P=NP. >
---
paper_title: Finding Largest Subtrees and Smallest Supertrees

paper_content:

As trees are used in a wide variety of application areas, the comparison of trees arises in many guises. Here we consider two generalizations of classical tree pattern matching, which consists of determining if one tree is isomorphic to a subgraph of another. For the embedding problems of subgraph isomorphism and topological embedding, we present algorithms for determining a largest tree embeddable in two trees T and T' (or a largest subtree) and a smallest tree in which each of T and T' can be embedded (or a smallest supertree). Both subtrees and supertrees can be used in a variety of different applications. For example, when each of the two trees contains partial information about a data set, such as the evolution of a set of species, the subtree or supertree corresponds to a structuring of the data in a manner consistent with both original trees. The size of a subtree or supertree of two trees can also be used to measure the similarity between two arrangements of data, whether images, documents, or RNA secondary structures.
---
paper_title: FINDING SMALLEST SUPERTREES UNDER MINOR CONTAINMENT

paper_content:

The diversity of application areas relying on tree-structured data results in wide interest in algorithms which determine differences or similarities among trees. One way of measuring the similarity between trees is to find the smallest common superstructure or supertree, where common elements are typically defined in terms of a mapping or embedding. In the simplest case, a supertree will contain exact copies of each input tree, so that for each input tree, each vertex of a tree can be mapped to a vertex in the supertree such that each edge maps to the corresponding edge. More general mappings allow for the extraction of more subtle common elements captured by looser definitions of similarity. We consider supertrees under the general mapping of minor containment. Minor containment generalizes both subgraph isomorphism and topological embedding; as a consequence of this generality, however, it is NP-complete to determine whether or not G is a minor of H, even for genreal trees. By focusing on trees of bounded degree, we obtain an O(n3) algorithm which determines the smallest tree T such that both of the input trees are minors of T, even when the trees are assumed to be unrooted and unordered.
---
paper_title: Indexing based on edit-distance matching of shape graphs

paper_content:

We are investigating a graph matching approach for indexing into pictorial databases using shock graphs, a symmetry- based representation of shape. Each shape (or a collection of edge elements) is represented by a shock graph. Indexing of a query into a pictorial database is accomplished by comparing the corresponding shock graph to the graphs representing database elements and selecting the best match. This paper introduces a new metric for comparing shock graphs.
---
paper_title: THE TREE-TO-TREE EDITING PROBLEM

paper_content:

This paper describes the computing alogrithms for the tree distance based on the structure preserving mapping. The distance is defined as the minimum sum of the weights of edit operations needed to transform tree Tα to tree Tβ under restriction of the structure preserving mapping. The edit operations allow substituting a vertex of a tree to another, deleting a vertex of a tree and inserting a vertex to a tree. Proposed algorithms determine the distance between Tα and Tβ in time O(NαNβLα) or O(NαNβLβ), and in space O(NαNβ), where Nα, Nβ, Lα and Lβ are the number of vertices of Tα, Tβ, the number of’ leaves of Tα and Tβ, respectively. The time complexity is close to the unapproachable lowest bound O(NαNβ). Improved algorithms are presented. This tree distance can be applied to any problems including pattern recognition, syntactic tree comparison and classification, and tree comparison whose structures are important in structure preserving mapping.
---
paper_title: The Tree-to-Tree Correction Problem

paper_content:

The tree-to-tree correctmn problem Is to determine, for two labeled ordered trees T and T', the distance from T to T' as measured by the mlmmum cost sequence of edit operaUons needed to transform T into T' The edit operations investigated allow changing one node of a tree into another node, deleting one node from a tree, or inserting a node into a tree An algorithm Is presented which solves this problem m time O(V* V'*LZ* L'2), where V and V' are the numbers of nodes respectively of T and T', and L and L' are the maximum depths respectively of T and T' Possible apphcatmns are to the problems of measuring the similarity between trees, automatic error recovery and correction for programming languages, and determining the largest common substructure of two trees
---
paper_title: Computing the edit-distance between unrooted ordered trees

paper_content:

An ordered tree is a tree in which each node's incident edges are cyclically ordered; think of the tree as being embedded in the plane. Let A and B be two ordered trees. The edit distance between A and B is the minimum cost of a sequence of operations (contract an edge, uncontract an edge, modify the label of an edge) needed to transform A into B. We give an O(n3 log n) algorithm to compute the edit distance between two ordered trees.
---
paper_title: The Tree-to-Tree Correction Problem

paper_content:

The tree-to-tree correctmn problem Is to determine, for two labeled ordered trees T and T', the distance from T to T' as measured by the mlmmum cost sequence of edit operaUons needed to transform T into T' The edit operations investigated allow changing one node of a tree into another node, deleting one node from a tree, or inserting a node into a tree An algorithm Is presented which solves this problem m time O(V* V'*LZ* L'2), where V and V' are the numbers of nodes respectively of T and T', and L and L' are the maximum depths respectively of T and T' Possible apphcatmns are to the problems of measuring the similarity between trees, automatic error recovery and correction for programming languages, and determining the largest common substructure of two trees
---
paper_title: The String-to-String Correction Problem

paper_content:

The string-to-string correction problem is to determine the distance between two strings as measured by the minimum cost sequence of “edit operations” needed to change the one string into the other. The edit operations investigated allow changing one symbol of a string into another single symbol, deleting one symbol from a string, or inserting a single symbol into a string. An algorithm is presented which solves this problem in time proportional to the product of the lengths of the two strings. Possible applications are to the problems of automatic spelling correction and determining the longest subsequence of characters common to two strings.
---
paper_title: Computing the edit-distance between unrooted ordered trees

paper_content:

An ordered tree is a tree in which each node's incident edges are cyclically ordered; think of the tree as being embedded in the plane. Let A and B be two ordered trees. The edit distance between A and B is the minimum cost of a sequence of operations (contract an edge, uncontract an edge, modify the label of an edge) needed to transform A into B. We give an O(n3 log n) algorithm to compute the edit distance between two ordered trees.
---
paper_title: Simple fast algorithms for the editing distance between trees and related problems

paper_content:

Ordered labeled trees are trees in which the left-to-right order among siblings is significant. The distance between two ordered trees is considered to be the weighted number of edit operations (insert, delete, and modify) to transform one tree to another. The problem of approximate tree matching is also considered. Specifically, algorithms are designed to answer the following kinds of questions:1. What is the distance between two trees? 2. What is the minimum distance between $T_1 $ and $T_2 $ when zero or more subtrees can be removed from $T_2 $? 3. Let the pruning of a tree at node n mean removing all the descendants of node n. The analogous question for prunings as for subtrees is answered.A dynamic programming algorithm is presented to solve the three questions in sequential time $O(|T_1 | \times |T_2 | \times \min ({\textit{depth}}(T_1 ),{\textit{leaves}}(T_1 )) \times \min ({\textit{depth}}(T_2 ),{\textit{leaves}}(T_2 )))$ and space $O(|T_1 | \times |T_2 |)$ compared with $O(|T_1 | \times |T_2 | \t...
---
paper_title: Fast Algorithms for Finding Nearest Common Ancestors

paper_content:

We consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, “What is the nearest common ancester of vertices x and y?” We show that any pointer machine that solves this problem requires $\Omega (\log \log n)$ time per query in the worst case, where n is the total number of vertices in the trees. On the other hand, we present an algorithm for a random access machine with uniform cost measure (and a bound of $\Omega (\log n)$ on the number of bits per word) that requires $O(1)$ time per query and $O(n)$ preprocessing time, assuming that the collection of trees is static. For a version of the problem in which the trees can change between queries, we obtain an almost-linear-time (and linear-space) algorithm.
---
paper_title: Computing the edit-distance between unrooted ordered trees

paper_content:

An ordered tree is a tree in which each node's incident edges are cyclically ordered; think of the tree as being embedded in the plane. Let A and B be two ordered trees. The edit distance between A and B is the minimum cost of a sequence of operations (contract an edge, uncontract an edge, modify the label of an edge) needed to transform A into B. We give an O(n3 log n) algorithm to compute the edit distance between two ordered trees.
---
paper_title: On the editing distance between unordered labeled trees

paper_content:

This paper considers the problem of computing the editing distance between unordered, labeled trees. We give efficient polynomial-time algorithms for the case when one tree is a string or has a bounded number of leaves. By contrast, we show that the problem is NP-complete even for binary trees having a label alphabet of size two.
---
paper_title: Some MAX SNP-hard results concerning unordered labeled trees

paper_content:

Given two rooted, labeled, and unordered trees, we consider the problem of finding the largest common sub-tree and the problem of finding the edit distance between them. We show that both problems are MAX SNP-hard. This means that neither problem has a polynomial time approximation scheme (PTAS) unless P = NP.
---
paper_title: Proof Verification and Hardness of Approximation Problems

paper_content:

The class PCP(f(n),g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that used O(f(n)) random bits, queries O(g(n)) bits of its oracle and behaves as follows: If x in L then there exists an oracle y such that the machine accepts for all random choices but if x not in L then for every oracle y the machine rejects with high probability. Arora and Safra (1992) characterized NP as PCP(log n, (loglogn)/sup O(1)/). The authors improve on their result by showing that NP=PCP(logn, 1). The result has the following consequences: (1) MAXSNP-hard problems (e.g. metric TSP, MAX-SAT, MAX-CUT) do not have polynomial time approximation schemes unless P=NP; and (2) for some epsilon >0 the size of the maximal clique in a graph cannot be approximated within a factor of n/sup epsilon / unless P=NP. >
---
paper_title: A New Measure of Edit Distance between Labeled Trees

paper_content:

One of the most important problem in computational biology is the tree editing problem which is to determine the edit distance between two rooted labeled trees. It has been shown to have significant applications in both RNA secondary structures and evolutionary trees. Another viewpoint of considering this problem is to find an edit mapping with the minimum cost. By restricting the type of mapping, Zhang [7,8] and Richter [5] independently introduced the constrained edit distance and the structure respecting distance, respectively. They are, in fact, the same concept. In this paper, we define a new measure of the edit distance between two rooted labeled trees, called less-constrained edit distance, by relaxing the restriction of constrained edit mapping. Then we study the algorithmic complexities of computing the less-constrained edit distance between two rooted labeled trees. For unordered labeled trees, we show that this problem is NP-complete and even has no absolute approximation algorithm unless P = NP, which also implies that it is impossible to have a PTAS for the problem. For ordered labeled trees, we give a polynomial-time algorithm to solve the problem.
---
paper_title: A constrained edit distance between unordered labeled trees

paper_content:

This paper considers the problem of computing a constrained edit distance between unordered labeled trees. The problem of approximate unordered tree matching is also considered. We present dynamic programming algorithms solving these problems in sequential timeO(|T1|×|T2|×(deg(T1)+deg(T2))× log2(deg(T1)+deg(T2))). Our previous result shows that computing the edit distance between unordered labeled trees is NP-complete.
---
paper_title: A New Measure of Edit Distance between Labeled Trees

paper_content:

One of the most important problem in computational biology is the tree editing problem which is to determine the edit distance between two rooted labeled trees. It has been shown to have significant applications in both RNA secondary structures and evolutionary trees. Another viewpoint of considering this problem is to find an edit mapping with the minimum cost. By restricting the type of mapping, Zhang [7,8] and Richter [5] independently introduced the constrained edit distance and the structure respecting distance, respectively. They are, in fact, the same concept. In this paper, we define a new measure of the edit distance between two rooted labeled trees, called less-constrained edit distance, by relaxing the restriction of constrained edit mapping. Then we study the algorithmic complexities of computing the less-constrained edit distance between two rooted labeled trees. For unordered labeled trees, we show that this problem is NP-complete and even has no absolute approximation algorithm unless P = NP, which also implies that it is impossible to have a PTAS for the problem. For ordered labeled trees, we give a polynomial-time algorithm to solve the problem.
---
paper_title: A Tree-to-Tree Distance and Its Application to Cluster Analysis

paper_content:

A distance measure between two trees is proposed. Using the idea of language transformation, a tree can be derived from another by a series of transformations. The distance between the two trees is the minimum-cost sequence of transformations. Based on this definition, an algorithm that generates the distance for any two trees is presented. Cluster analysis for patterns represented by tree structures is discussed. Using a tree-to-tree distance, the similarity between patterns is measured in terms of distance between their tree representations. An illustrative example on clustering of character patterns is presented.
---
paper_title: Finding approximate patterns in strings

paper_content:

Let p (the pattern) be a string and t ≥ 0 an integer. The problem of locating in any string a substring whose edit distance from p is at most a given constant t is considered. An algorithm is presented to construct a deterministic finite-state automaton that solves the problem.
---
paper_title: Fast parallel and serial approximate string matching

paper_content:

Consider the string matching problem, where differences between characters of the pattern and characters of the text are allowed. Each difference is due to either a mismatch between a character of the text and a character of the pattern, or a superfluous character in the text, or a superfluous character in the pattern. Given a text of lenght n, a pattern of length m and an integer k, we present parallel and serial algorthms for finding all occurrences of the pattern in the text with at most k differences. The parallel algorithm requires O(log m + k) time using n processors. The serial algorithm runs in O(nk) time for an alphabet whose size is fixed.
---
paper_title: THE TREE-TO-TREE EDITING PROBLEM

paper_content:

This paper describes the computing alogrithms for the tree distance based on the structure preserving mapping. The distance is defined as the minimum sum of the weights of edit operations needed to transform tree Tα to tree Tβ under restriction of the structure preserving mapping. The edit operations allow substituting a vertex of a tree to another, deleting a vertex of a tree and inserting a vertex to a tree. Proposed algorithms determine the distance between Tα and Tβ in time O(NαNβLα) or O(NαNβLβ), and in space O(NαNβ), where Nα, Nβ, Lα and Lβ are the number of vertices of Tα, Tβ, the number of’ leaves of Tα and Tβ, respectively. The time complexity is close to the unapproachable lowest bound O(NαNβ). Improved algorithms are presented. This tree distance can be applied to any problems including pattern recognition, syntactic tree comparison and classification, and tree comparison whose structures are important in structure preserving mapping.
---
paper_title: Algorithms on strings, trees, and sequences

paper_content:

Linear-Time Construction of Suffix Trees We will present two methods for constructing suffix trees in detail, Ukkonen’s method and Weiner’s method. Weiner was the first to show that suffix trees can be built in linear time, and his method is presented both for its historical importance and for some different technical ideas that it contains. However, lJkkonen’s method is equally fast and uses far less space (i.e., memory) in practice than Weiner’s method Hence Ukkonen is the method of choice for most problems requiring the construction of a suffix tree. We also believe that Ukkonen’s method is easier to understand. Therefore, it will be presented first A reader who wishes to study only one method is advised to concentrate on it. However, our development of Weiner’s method does not depend on understanding Ukkonen’s algorithm, and the two algorithms can be read independently (with one small shared section noted in the description of Weiner’s method).
---
paper_title: Alignment of Trees - An Alternative to Tree Edit

paper_content:

In this paper, we propose the alignment of trees as a measure of the similarity between two labeled trees. Both ordered and unordered trees are considered. An algorithm is designed for ordered trees. The time complexity of this algorithm is O(¦T1¦· s¦T2· (deg(T1) + deg(T2))2), where ¦Ti¦ is the number of nodes in T i and deg(T i ) is the degree of T i , i=1,2. The algorithm is faster than the best known algorithm for tree edit when deg(T1) and deg(T2) are smaller than the depths of T1 and T2. For unordered trees, we show that the alignment problem can be solved in polynomial time if the trees have a bounded degree and becomes NP-hard if one of the trees is allowed to have an arbitrary degree. In contrast, the edit problem for unordered trees is NP-hard even if both trees have a bounded degree [17]. Finally, multiple alignment of trees is discussed.
---
paper_title: Alignment of Trees - An Alternative to Tree Edit

paper_content:

In this paper, we propose the alignment of trees as a measure of the similarity between two labeled trees. Both ordered and unordered trees are considered. An algorithm is designed for ordered trees. The time complexity of this algorithm is O(¦T1¦· s¦T2· (deg(T1) + deg(T2))2), where ¦Ti¦ is the number of nodes in T i and deg(T i ) is the degree of T i , i=1,2. The algorithm is faster than the best known algorithm for tree edit when deg(T1) and deg(T2) are smaller than the depths of T1 and T2. For unordered trees, we show that the alignment problem can be solved in polynomial time if the trees have a bounded degree and becomes NP-hard if one of the trees is allowed to have an arbitrary degree. In contrast, the edit problem for unordered trees is NP-hard even if both trees have a bounded degree [17]. Finally, multiple alignment of trees is discussed.
---
paper_title: Alignment of Trees - An Alternative to Tree Edit

paper_content:

In this paper, we propose the alignment of trees as a measure of the similarity between two labeled trees. Both ordered and unordered trees are considered. An algorithm is designed for ordered trees. The time complexity of this algorithm is O(¦T1¦· s¦T2· (deg(T1) + deg(T2))2), where ¦Ti¦ is the number of nodes in T i and deg(T i ) is the degree of T i , i=1,2. The algorithm is faster than the best known algorithm for tree edit when deg(T1) and deg(T2) are smaller than the depths of T1 and T2. For unordered trees, we show that the alignment problem can be solved in polynomial time if the trees have a bounded degree and becomes NP-hard if one of the trees is allowed to have an arbitrary degree. In contrast, the edit problem for unordered trees is NP-hard even if both trees have a bounded degree [17]. Finally, multiple alignment of trees is discussed.
---
paper_title: Alignment of Trees - An Alternative to Tree Edit

paper_content:

In this paper, we propose the alignment of trees as a measure of the similarity between two labeled trees. Both ordered and unordered trees are considered. An algorithm is designed for ordered trees. The time complexity of this algorithm is O(¦T1¦· s¦T2· (deg(T1) + deg(T2))2), where ¦Ti¦ is the number of nodes in T i and deg(T i ) is the degree of T i , i=1,2. The algorithm is faster than the best known algorithm for tree edit when deg(T1) and deg(T2) are smaller than the depths of T1 and T2. For unordered trees, we show that the alignment problem can be solved in polynomial time if the trees have a bounded degree and becomes NP-hard if one of the trees is allowed to have an arbitrary degree. In contrast, the edit problem for unordered trees is NP-hard even if both trees have a bounded degree [17]. Finally, multiple alignment of trees is discussed.
---
paper_title: More Efficient Algorithm for Ordered Tree Inclusion

paper_content:

Given two ordered trees S and T, the tree inclusion problem is to determine whether it is possible to obtain S from T by deleting nodes. Recently, this problem has been recognized as an important primitive in query processing for structured text databases. In this paper we present anO(|leaves(S)||T|) time andO(|leaves(S)|min(depth(T),|leaves(T)|)) space algorithm for ordered tree inclusion, by means of a sophisticated bottom-up-matching strategy. Our algorithm improves the previous best one (Kilpel?inen, 1992, Ph.D. thesis, Dept. Computer Science, Univ. Helsinki) that requiresO(|S||T|) time andO(|S|min(depth(T),|leaves(T)|)) space.
---
paper_title: Ordered and Unordered Tree Inclusion

paper_content:

The following tree-matching problem is considered: Given labeled trees $P$ and $T$, can $P$ be obtained from $T$ by deleting nodes? Deleting a node $u$ entails removing all edges incident to $u$ and, if $u$ has a parent $v$, replacing the edge from $v$ to $u$ by edges from $v$ to the children of $u$. The problem is motivated by the study of query languages for structured text databases. Simple solutions to this problem require exponential time. For ordered trees an algorithm is presented that requires $O(|P| |T|)$ time and space. The corresponding problem for unordered trees is also considered and a proof of its NP-completeness is given. An algorithm is presented for the unordered problem. This algorithm works in $O(|P| |T|)$ time if the out-degrees of the nodes in $P$ are bounded by a constant, and in polynomial time if they are $O(\log |T|)$.
---
paper_title: More Efficient Algorithm for Ordered Tree Inclusion

paper_content:

Given two ordered trees S and T, the tree inclusion problem is to determine whether it is possible to obtain S from T by deleting nodes. Recently, this problem has been recognized as an important primitive in query processing for structured text databases. In this paper we present anO(|leaves(S)||T|) time andO(|leaves(S)|min(depth(T),|leaves(T)|)) space algorithm for ordered tree inclusion, by means of a sophisticated bottom-up-matching strategy. Our algorithm improves the previous best one (Kilpel?inen, 1992, Ph.D. thesis, Dept. Computer Science, Univ. Helsinki) that requiresO(|S||T|) time andO(|S|min(depth(T),|leaves(T)|)) space.
---
paper_title: On the tree inclusion problem

paper_content:

Abstract. We consider the following problem: Given ordered labeled trees S and T can S be obtained from T by deleting nodes? Deletion of the root node u of a subtree with children ::: $(T_1, \ldots,T_n)$ means replacing the subtree by the trees ::: $T_1, \ldots,T_n$. For the tree inclusion problem, there can generally be exponentially many ways to obtain the included tree. P. Kilpelinen and H. Mannila [5,7] gave an algorithm based on dynamic programming requiring ::: $O(\mid S\mid.\mid T \mid)$ time and space in the worst case and also on the average for solving this problem. We give an algorithm whose idea is similar to that of [5,7] but which improves the previous one and on the average breaks the ::: $\mid S\mid.\mid T \mid$ barrier.
---
paper_title: Tree Matching Problems with Applications to Structured Text Databases

paper_content:

A venturi scrubber for the scrubbing of an inlet gas stream with a scrubbing liquid or slurry, to remove gaseous or vaporous components from the gas stream, or to remove entrained solid particulate or discrete liquid droplet (fog or mist) constituents, and thereby to prevent air pollution and/or to recover the component or constituent. The venturi scrubber has an adjustable throat characterized by the provision of structure to adjust the cross-sectional dimension of the gas passage at or adjacent to the throat section. The structure includes at least one movable baffle at the periphery of the gas passage, and a container. The container is disposed external to and contiguous with the baffle, and a controlled amount of a fluid is passed into the container so that the internal fluid pressure within the container, and resultant volumetric dimension of the container, and thereby also the resultant displacement of the baffle relative to the periphery of the throat section, are adjustable in proportion to a change in the flow rate of the inlet gas stream.
---
paper_title: Ordered and Unordered Tree Inclusion

paper_content:

The following tree-matching problem is considered: Given labeled trees $P$ and $T$, can $P$ be obtained from $T$ by deleting nodes? Deleting a node $u$ entails removing all edges incident to $u$ and, if $u$ has a parent $v$, replacing the edge from $v$ to $u$ by edges from $v$ to the children of $u$. The problem is motivated by the study of query languages for structured text databases. Simple solutions to this problem require exponential time. For ordered trees an algorithm is presented that requires $O(|P| |T|)$ time and space. The corresponding problem for unordered trees is also considered and a proof of its NP-completeness is given. An algorithm is presented for the unordered problem. This algorithm works in $O(|P| |T|)$ time if the out-degrees of the nodes in $P$ are bounded by a constant, and in polynomial time if they are $O(\log |T|)$.
---
paper_title: Ordered and Unordered Tree Inclusion

paper_content:

The following tree-matching problem is considered: Given labeled trees $P$ and $T$, can $P$ be obtained from $T$ by deleting nodes? Deleting a node $u$ entails removing all edges incident to $u$ and, if $u$ has a parent $v$, replacing the edge from $v$ to $u$ by edges from $v$ to the children of $u$. The problem is motivated by the study of query languages for structured text databases. Simple solutions to this problem require exponential time. For ordered trees an algorithm is presented that requires $O(|P| |T|)$ time and space. The corresponding problem for unordered trees is also considered and a proof of its NP-completeness is given. An algorithm is presented for the unordered problem. This algorithm works in $O(|P| |T|)$ time if the out-degrees of the nodes in $P$ are bounded by a constant, and in polynomial time if they are $O(\log |T|)$.
---
paper_title: On the complexity of finding iso- and other morphisms for partial k-trees

paper_content:

Abstract The problems to decide whether H ⩽ G for input graphs H , G where ⩽ is ‘isomorphic to a subgraph’, ‘isomorphic to an induced subgraphs’, ‘isomorphic to a subdivision’, ‘isomorphic to a contraction’ or their combination, are NP-complete. We discuss the complexity of these problems when G is restricted to be a partial k -tree (in other terminology: to have tree-width ⩽ k , to be k -decomposable, to have dimension ⩽ k ). Under this restriction the problems are still NP-complete in general, but there are polynomial algorithms under some natural restrictions imposed on H , for example when H has bounded degrees. We also give a polynomial time algorithm for the n disjoint connecting paths problem restricted to partial k -trees (with n part of input).
---
paper_title: Computing the edit-distance between unrooted ordered trees

paper_content:

An ordered tree is a tree in which each node's incident edges are cyclically ordered; think of the tree as being embedded in the plane. Let A and B be two ordered trees. The edit distance between A and B is the minimum cost of a sequence of operations (contract an edge, uncontract an edge, modify the label of an edge) needed to transform A into B. We give an O(n3 log n) algorithm to compute the edit distance between two ordered trees.
---
paper_title: Meaningful Change Detection in Structured Data

paper_content:

Detecting changes by comparing data snapshots is an important requirement for difference queries, active databases, and version and configuration management. In this paper we focus on detecting meaningful changes in hierarchically structured data, such as nested-object data. This problem is much more challenging than the corresponding one for relational or flat-file data. In order to describe changes better, we base our work not just on the traditional “atomic” insert, delete, update operations, but also on operations that move an entire sub-tree of nodes, and that copy an entire sub-tree. These operations allows us to describe changes in a semantically more meaningful way. Since this change detection problem is NP -hard, in this paper we present a heuristic change detection algorithm that yields close to “minimal” descriptions of the changes, and that has fewer restrictions than previous algorithms. Our algorithm is based on transforming the change detection problem to a problem of computing a minimum-cost edge cover of a bipartite graph. We study the quality of the solution produced by our algorithm, as well as the running time, both analytically and experimentally.
---
paper_title: A tree-edit-distance algorithm for comparing simple, closed shapes

paper_content:

A b s t r a c t We discuss a graph-algorithmic approach to comparing shapes. We focus in this paper on comparing simple closed curves in the plane. Our approach is to (1) represent such a shape by its skeleton, which is a tree embedded in the plane, and (2) compare two shapes by comparing their skeletons via tree edit-distance. In this paper, we define our version of tree edit-distance (it differs from that previously described in the literature), and give a polynomial-time algorithm to compute the distance between two trees.
---
paper_title: Change detection in hierarchically structured information

paper_content:

Detecting and representing changes to data is important for active databases, data warehousing, view maintenance, and version and configuration management. Most previous work in change management has dealt with flat-file and relational data; we focus on hierarchically structured data. Since in many cases changes must be computed from old and new versions of the data, we define the hierarchical change detection problem as the problem of finding a "minimum-cost edit script" that transforms one data tree to another, and we present efficient algorithms for computing such an edit script. Our algorithms make use of some key domain characteristics to achieve substantially better performance than previous, general-purpose algorithms. We study the performance of our algorithms both analytically and empirically, and we describe the application of our techniques to hierarchically structured documents.
---

Title: A Survey on Tree Edit Distance and Related Problems

Section 1: Introduction
Description 1: Introduce the common combinatorial structure of trees in computer science and their applications. Define labeled and ordered trees, and the basic edit operations.

Section 2: Preliminaries and notation
Description 2: Define notation and preliminary definitions used throughout the paper. Include terms like depth, degree, leaves of trees, and introduce the concept of forests and cost functions.

Section 3: Tree Edit Distance
Description 3: Survey the tree edit distance problem. Define edit scripts and mappings, and discuss techniques and algorithms for both ordered and unordered trees. Include constraints and variants of the problem.

Section 4: Edit operations and edit mappings
Description 4: Detail how edit operations and mappings are defined for labeled trees and their costs. Include formal definitions and metrics used in measuring distances.

Section 5: General ordered edit distance
Description 5: Discuss the ordered edit distance problem, present basic recursion and dynamic programming algorithms, and highlight improvements made by specific algorithms.

Section 6: Zhang and Shasha's algorithm
Description 6: Present Zhang and Shasha’s algorithm in detail, including keyroots, relevant subproblems, and collapsed depth concepts.

Section 7: General unordered edit distance
Description 7: Survey the unordered edit distance problem, discuss its complexity issues, and highlight polynomial algorithms for special cases.

Section 8: Constrained edit distance
Description 8: Discuss restricted versions of the edit distance problem, including constrained and structure-respecting edit distances. Present algorithms and their complexities for these constrained problems.

Section 9: Other variants
Description 9: Survey other edit distance variants, like unit cost edit distance, 1-degree edit distance, and edit operations on subtrees. Present different approaches and algorithms for these problems.

Section 10: Tree Alignment Distance
Description 10: Introduce the tree alignment distance problem, define the concept of alignment and metric cost functions. Compare tree alignment distance with edit distance.

Section 11: Ordered tree alignment distance
Description 11: Detail the ordered tree alignment distance problem, present existing algorithms and their complexities.

Section 12: Jiang, Wang, and Zhang's algorithm
Description 12: Present the algorithm of Jiang, Wang, and Zhang for ordered tree alignment. Include detailed steps and dynamic programming approach.

Section 13: Unordered tree alignment distance
Description 13: Discuss the algorithm modifications for unordered tree alignment and present complexity results for trees with bounded degrees.

Section 14: Tree Inclusion
Description 14: Survey the tree inclusion problem, define inclusion through edge deletions, and discuss known results.

Section 15: Orderings and embeddings
Description 15: Define orderings of nodes, left and right relatives, and ordered embeddings. Present the conditions for embeddings.

Section 16: Ordered tree inclusion
Description 16: Present the ordered tree inclusion problem, algorithms, and improvements by different researchers. Include detailed analysis of Kilpeläinen and Mannila’s algorithm.

Section 17: Unordered tree inclusion
Description 17: Discuss the NP-completeness of the unordered tree inclusion problem and present known algorithms.

Section 18: Conclusion
Description 18: Summarize the surveyed problems and algorithms. Present open problems and future research directions.