ダウンロード数: 85
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
LIPIcs-ISAAC-2022-44.pdf | 730.66 kB | Adobe PDF | 見る/開く |
タイトル: | On the complexity of tree edit distance with variables |
著者: | Akutsu, Tatsuya ![]() ![]() ![]() Mori, Tomoya Nakamura, Naotoshi Kozawa, Satoshi Ueno, Yuhei Sato, Thomas N |
著者名の別形: | 阿久津, 達也 森, 智弥 |
キーワード: | Tree edit distance unification parameterized algorithms |
発行日: | 2022 |
出版者: | Schloss Dagstuhl Leibniz-Zentrum für Informatik |
誌名: | 33rd International Symposium on Algorithms and Computation (ISAAC 2022) |
巻: | 248 |
開始ページ: | 44:1 |
終了ページ: | 44:14 |
抄録: | In this paper, we propose tree edit distance with variables, which is an extension of the tree edit distance to handle trees with variables and has a potential application to measuring the similarity between mathematical formulas. We analyze the computational complexity of several variants of this model. In particular, we show that the problem is NP-complete for ordered trees. We also show for unordered trees that the problem of deciding whether or not the distance is 0 is graph isomorphism complete but can be solved in polynomial time if the maximum outdegree of input trees is bounded by a constant. We also present parameterized and exponential-time algorithms for ordered and unordered cases, respectively. |
記述: | Leibniz International Proceedings in Informatics (LIPIcs) |
著作権等: | © Tatsuya Akutsu, Tomoya Mori, Naotoshi Nakamura, Satoshi Kozawa, Yuhei Ueno, and Thomas N. Sato Licensed under Creative Commons License CC-BY 4.0 |
URI: | http://hdl.handle.net/2433/282031 |
DOI(出版社版): | 10.4230/LIPIcs.ISAAC.2022.44 |
出現コレクション: | 学術雑誌掲載論文等 |
![](/dspace/image/articlelinker.gif)
このアイテムは次のライセンスが設定されています: クリエイティブ・コモンズ・ライセンス