| 講演名 | 1996/1/26 木の距離の並列計算法 山元 雅博, 田中 榮一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 根があり順序がある木(RO木)の距離に関して, 幾つかの定義とそれらの計算法が提案されている. その一つに, 強構造保存写像に基づく距離(SSPD)がある. 本論文では, CREW PRAM上でSSPDの値を計算する並列アルゴリズムを提案する. 頂点数がNα, Nβである2つのRO木Tα, Tβが与えられた時, 提案するアルゴリズムはO((NαNβ)/(Nα+Nβ))個のプロセッサを用いて, 時間計算量O(Nα+Nβ), 領域計算量O(NαNβ)でSSPDの値を求めることができる. この時のコストはO(NαNβ)であり, SSPDの値を求める逐次アルゴリズムの時間計算量と一致する. |
| 抄録(英) | Several definitions and computing methods for the distance between rooted and ordered trees(RO-trees) were proposed. The strongly structure preserving distance (SSPD) is one of them. This paper describes a parallel algorithm for computing SSPD. The algorithm runs on the CREW PRAM model, and computes SSPD between RO-trees Tα and Tβ in time O(Nα+Nβ) with O ((NαNβ)/(Nα+Nβ)) proceccors, where Nα and Nβ are the numbers of vertices of the two trees. The space complexity is O(NαNβ). The cost of this algorithm is O(NαNβ), and is equal to the time complexity of a serial algorithm for computing SSPD. |
| キーワード(和) | 並列アルゴリズム / 木 / 距離 / パターンマッチング / パターン認識 |
| キーワード(英) | parallel algorithm / tree / distance / pattern matching / pattern recognition |
| 資料番号 | COMP95-73 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1996/1/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 木の距離の並列計算法 |
| サブタイトル（和） | |
| タイトル（英） | A Parallel Algorithm for a Tree Distance |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 並列アルゴリズム / parallel algorithm |
| キーワード(2)（和/英） | 木 / tree |
| キーワード(3)（和/英） | 距離 / distance |
| キーワード(4)（和/英） | パターンマッチング / pattern matching |
| キーワード(5)（和/英） | パターン認識 / pattern recognition |
| 第 1 著者 氏名（和/英） | 山元 雅博 / Masahiro YAMAMOTO |
| 第 1 著者 所属（和/英） | 神戸大学大学院自然科学研究科 Graduate School of Science and Technology, Kobe University |
| 第 2 著者 氏名（和/英） | 田中 榮一 / Eiichi TANAKA |
| 第 2 著者 所属（和/英） | 神戸大学工学部 Faculty of Engineering, Kobe University |
| 発表年月日 | 1996/1/26 |
| 資料番号 | COMP95-73 |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 498 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |