講演抄録/キーワード |
講演名 |
2012-06-21 11:00
Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees Tatsuya Akutsu・○Takeyuki Tamura(Kyoto Univ.)・Daiji Fukagawa(Doshisha Univ.)・Atsuhiro Takasu(NII) COMP2012-15 |
抄録 |
(和) |
本稿ではNP困難問題として知られる無順序木の編集距離の効率的な指数時間アルゴリズムを扱う。$n_1$と$n_2$を2つの入力の木のノード数とすると、一般の場合に対する$O(1.26^{n_1+n_2})$時間アルゴリズムを示す。このアルゴリズムは動的計画法、全探索、最大重み付き二部マッチングを組み合わせて得られる。また、次数が制限されアルファベットが固定の時には、任意の定数$\epsilon > 0$に対し、$O((1+\epsilon)^{n_1+n_2})$時間でこの問題が解けることを示す。この結果は、小さい部分木内の同じ部分集合に対する再計算を避けることにより得られたものである。 |
(英) |
This report presents efficient exponential time algorithms for the unordered tree edit distance problem, which is known to be NP-hard.
For a general case, an $O(1.26^{n_1+n_2})$ time algorithm is presented, where $n_1$ and $n_2$ are the numbers of nodes in two input trees. This algorithm is obtained by a combination of dynamic programming, exhaustive search, and maximum weighted bipartite matching. For bounded degree trees over a fixed alphabet, it is shown that the problem can be solved in $O((1+\epsilon)^{n_1+n_2})$ time for any fixed $\epsilon > 0$. This result is achieved by avoiding duplicate calculations for identical subsets of small subtrees. |
キーワード |
(和) |
木の編集距離 / 無順序木 / 動的計画法 / 最大重み付き二部マッチング / / / / |
(英) |
tree edit distance / unordered trees / dynamic programming / maximum weight bipartite matching / / / / |
文献情報 |
信学技報, vol. 112, no. 93, COMP2012-15, pp. 25-31, 2012年6月. |
資料番号 |
COMP2012-15 |
発行日 |
2012-06-14 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-15 |