このアイテムのアクセス数: 552
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| j.tcs.2010.10.002.pdf | 182.42 kB | Adobe PDF | 見る/開く |
| タイトル: | Exact algorithms for computing the tree edit distance between unordered trees |
| 著者: | Akutsu, Tatsuya    https://orcid.org/0000-0001-9763-797X (unconfirmed)Fukagawa, Daiji Takasu, Atsuhiro Tamura, Takeyuki https://orcid.org/0000-0003-1596-901X (unconfirmed) |
| 著者名の別形: | 阿久津, 達也 |
| キーワード: | Tree edit distance Fixed-parameter algorithms Dynamic programming Unordered trees |
| 発行日: | 4-Feb-2011 |
| 出版者: | Elsevier B.V. |
| 誌名: | Theoretical Computer Science |
| 巻: | 412 |
| 号: | 4-5 |
| 開始ページ: | 352 |
| 終了ページ: | 364 |
| 抄録: | This paper presents a fixed-parameter algorithm for the tree edit distance problem for unordered trees under the unit cost model that works in O(2.62^k⋅poly(n)) time and O(n^2) space, where the parameter k is the maximum bound of the edit distance and n is the maximum size of input trees. This paper also presents polynomial-time algorithms for the case where the maximum degree of the largest common subtree is bounded by a constant |
| 著作権等: | © 2010 Elsevier B.V. This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
| URI: | http://hdl.handle.net/2433/149243 |
| DOI(出版社版): | 10.1016/j.tcs.2010.10.002 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。