| 講演名 | 1996/9/17 共通部分木と編集距離に対する近似および特殊な場合 ハルダースソン マグナス, 田中 圭介, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 二つのラベルつき順序なしの木が与えられたとする. このとき, 共通部分木問題は, ラベルと祖先関係を保つ最大濃度の木の, 頂点部分集合間の一対一のマッチングを見つける問題である. また, 木編集距離問題は, ひとつの木から別の木へ変換する, 追加, 削除, 変更の最小コストの列を決める問題である. 両方の問題とも, 一般的には, ある定数で近似するのは難しいことが知られている. 我々は, よりきつい近似困難性の証明を与えると共に, いくつかの特殊な木のクラスに対する多項式アルゴリズムを提案する. このことにより, 全ての興味深い木の特殊なクラスに対する, 両方の問題の複雑さの特徴づけに近づいたことになる. 我々はまた, 最初の自明でない近似率をもつ近似アルゴリズムを提案する. 特に, nを小さい木の頂点数とすると, 近似率log^2 nを達成する. |
| 抄録(英) | Given two rooted, labeled, unordered trees, the common subtree problem is to find a bijective matching between subsets of vertices of the trees of maximum cardinality which preserves labels and ancestry relationship. The tree editing distance problem is to determine the least cost sequence of additions, deletions and changes that converts one tree into the other input tree. Both problems are known to be hard to approximate within some constant factor in general. We present polynomial algorithms for several special classes of trees as well as a tighter approximation hardness proof, which together comes close to characterizing the complexity of both problems on all interesting special classes of trees. We also present the first approximation algorithm with non-trivial approximation ratios. In particular, we achieve a ratio of log^2 n, where n is the number of vertices in the smaller tree. |
| キーワード(和) | 共通部分木 / 編集距離 / 近似 / 計算の複雑さ |
| キーワード(英) | common subtree / editing distance / approximation / computational complexity |
| 資料番号 | COMP96-28 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1996/9/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 共通部分木と編集距離に対する近似および特殊な場合 |
| サブタイトル（和） | |
| タイトル（英） | Approximation and Special Cases of Common Subtrees and Editing Distance |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 共通部分木 / common subtree |
| キーワード(2)（和/英） | 編集距離 / editing distance |
| キーワード(3)（和/英） | 近似 / approximation |
| キーワード(4)（和/英） | 計算の複雑さ / computational complexity |
| 第 1 著者 氏名（和/英） | ハルダースソン マグナス / Magnus M. Halldorsson |
| 第 1 著者 所属（和/英） | Science Institute University of Iceland Science Institute University of Iceland |
| 第 2 著者 氏名（和/英） | 田中 圭介 / Keisuke Tanaka |
| 第 2 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information Science Japan Advanced Institute of Science and Technology-Hokuriku |
| 発表年月日 | 1996/9/17 |
| 資料番号 | COMP96-28 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 250 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |