| 講演名 | 2012-06-21 無順序木の編集距離の指数時間厳密アルゴリズム 阿久津 達也, 田村 武幸, 深川 大路, 高須 淳宏, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿ではNP困難問題として知られる無順序木の編集距離の効率的な指数時間アルゴリズムを扱う。n_1とn_2を2つの入力の木のノード数とすると、一般の場合に対するO(1.26^ |
| 抄録(英) | 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^ |
| キーワード(和) | 木の編集距離 / 無順序木 / 動的計画法 / 最大重み付き二部マッチング |
| キーワード(英) | tree edit distance / unordered trees / dynamic programming / maximum weight bipartite matching |
| 資料番号 | COMP2012-15 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2012/6/14(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 無順序木の編集距離の指数時間厳密アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 木の編集距離 / tree edit distance |
| キーワード(2)（和/英） | 無順序木 / unordered trees |
| キーワード(3)（和/英） | 動的計画法 / dynamic programming |
| キーワード(4)（和/英） | 最大重み付き二部マッチング / maximum weight bipartite matching |
| 第 1 著者 氏名（和/英） | 阿久津 達也 / Tatsuya AKUTSU |
| 第 1 著者 所属（和/英） | 京都大学化学研究所バイオインフォマティクスセンター Bioinformatics Center, Institute for Chemical Research, Kyoto University |
| 第 2 著者 氏名（和/英） | 田村 武幸 / Takeyuki TAMURA |
| 第 2 著者 所属（和/英） | 京都大学化学研究所バイオインフォマティクスセンター Bioinformatics Center, Institute for Chemical Research, Kyoto University |
| 第 3 著者 氏名（和/英） | 深川 大路 / Daiji FUKAGAWA |
| 第 3 著者 所属（和/英） | 同志社大学文化情報学部 Faculty of Culture and Information Science, Doshisha University |
| 第 4 著者 氏名（和/英） | 高須 淳宏 / Atsuhiro TAKASU |
| 第 4 著者 所属（和/英） | 国立情報学研究所 National Institute of Informatics |
| 発表年月日 | 2012-06-21 |
| 資料番号 | COMP2012-15 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 93 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |