Name
Abstract | ||
|---|---|---|
In this paper, we investigate the problem of computing structural sensitive variations of an unordered tree edit (listance. First, we focus on the variations tractable by the algorithms including the submodule of a network algorithm, either the minimum cost maximum flow algorithm or the maximum weighted bipartite matching algorithm. Then, we show that both network algorithms are replaceable, and hence the time complexity of computing these variations can be reduced to (nrnd) time, where it is the number of nodes in a tree, m is the number of nodes in another tree and d is the in degree of given two trees. Next, we show that the problem of computing the bottom-up distance is MAX SNP-hard. Note that the well linear tune algorithm for the bottom -up distance designed by Valiente (2001) computes just a bottom-up iode (insertion-deletion) distance allowing no substitutions. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1142/S0129054114500154 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
Tree edit distance, unordered tree, variations of Tai mapping, variations of tree edit distance | Edit distance,Discrete mathematics,Range tree,Combinatorics,Wagner–Fischer algorithm,K-ary tree,Algorithm,Tree structure,Segment tree,Gomory–Hu tree,Mathematics,Interval tree | Journal |
Volume | Issue | ISSN |
25 | 3 | 0129-0541 |
Citations | PageRank | References |
1 | 0.38 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoshiyuki Yamamoto | 1 | 1 | 0.38 |
| Kouichi Hirata | 2 | 130 | 32.04 |
| Tetsuji Kuboyama | 3 | 140 | 29.36 |