| 講演名 | 1994/11/18 平面に埋め込まれた木の最大類似部分を求めるアルゴリズム 劉 紹明, 田中 榮一, 増田 澄男, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では,根があり順序がある2つの木,及び平面に埋め込まれた2つの木T_a,T_bについて,T_aと類似している部分をT_b内で探す問題を論じている.木の最大類似部分を表すため,木の間の極大C写像及びそれに基づくT_bの中の"T_aとの最大類似部分"を定義し,その最大類似部分の1つを抽出するアルゴリズムを述べている.このアルゴリズムの時間計算量と空間計算量は,根があり順序がある木では,それぞれΟ_T(N_aN_b)とΟ_S(N_aN_b)であり,平面に埋め込まれた木では,それぞれΟ_T(m_am_bN_aN_b)とΟ_S((m_a+m_b)N_a+N_b)である.ここで,N_a(N_b)とm_a(m_b)は,それぞれT_a(T_b)の頂点数と最大の頂点次数を表す. |
| 抄録(英) | This paper discusses the problems of finding similar substructures in tree T_b to tree T_a,where,both T_a and T_b are rooted and ordered trees(RO-trees),or trees embedded in a plane(unrooted and cyclically ordered trees:CO-trees).We define a maximum C mapping between RO-trees(CO-trees)and largest similar substructures in T_b to T_a based on that mapping,and propose two algorithms for finding one of the largest similar substructures for RO-trees and that for CO-trees.The time and space complexities of the algorithm for RO-trees are Ο_T(N_aN_b)and Ο_S(N_aN_b),resp ectively,and those of the algorithm for CO-trees are Ο_T(m_am_bN_a N_b)and Ο_S((m_a+m_b)N_aN_b),respectively,where N_a(N_b)and m_a(m_ b)are the number of vertices of T_a(T_b)and the largest degree of a vertex,respectively. |
| キーワード(和) | 類似部分グラフ / 木 / アルゴリズム / 距離 / 計算量 / パターンマッチング |
| キーワード(英) | similar subgraph / tree / algorithm / distance / complexity / pattern matching |
| 資料番号 | COMP94-57 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1994/11/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 平面に埋め込まれた木の最大類似部分を求めるアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An Algorithm for the Largest Similar Substructures between Trees Embedded in a Plane |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 類似部分グラフ / similar subgraph |
| キーワード(2)（和/英） | 木 / tree |
| キーワード(3)（和/英） | アルゴリズム / algorithm |
| キーワード(4)（和/英） | 距離 / distance |
| キーワード(5)（和/英） | 計算量 / complexity |
| キーワード(6)（和/英） | パターンマッチング / pattern matching |
| 第 1 著者 氏名（和/英） | 劉 紹明 / Shaoming Liu |
| 第 1 著者 所属（和/英） | 神戸大学大学院自然科学研究科 The Graduate School of Science and Technology,Kobe University |
| 第 2 著者 氏名（和/英） | 田中 榮一 / Eiichi Tanaka |
| 第 2 著者 所属（和/英） | 神戸大学工学部電気電子工学科 Department of Electrical and Electronics Engineering,Faculty of Engineering,Kobe University |
| 第 3 著者 氏名（和/英） | 増田 澄男 / Sumio Masuda |
| 第 3 著者 所属（和/英） | 神戸大学工学部電気電子工学科 Department of Electrical and Electronics Engineering,Faculty of Engineering,Kobe University |
| 発表年月日 | 1994/11/18 |
| 資料番号 | COMP94-57 |
| 巻番号（vol） | vol.94 |
| 号番号（no） | 354 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |