Name
Abstract | ||
|---|---|---|
In this paper, we give an approximation of the tree edit distance through the string edit distance for binary tree codes, instead of one for Euler strings introduced by Akutsu (2006). Here, a binary tree code is a string obtained by traversing a binary tree representation with two kinds of dummy nodes of a tree in preorder. Then, we show that σ/2 ≤ τ ≤ (h + 1)σ + h, where τ is the tree edit distance between trees, σ is the string edit distance between their binary tree codes and h is the minimum height of the trees. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-540-95891-8_12 | Fundam. Inform. |
Keywords | DocType | Volume |
euler string,binary tree representation,dummy node,string edit distance,approximating tree edit distance,binary tree code,binary tree codes,minimum height,binary tree | Conference | 101 |
Issue | ISSN | Citations |
3 | 0169-2968 | 1 |
PageRank | References | Authors |
0.37 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Taku Aratsu | 1 | 3 | 0.77 |
| Kouichi Hirata | 2 | 130 | 32.04 |
| Tetsuji Kuboyama | 3 | 140 | 29.36 |