| 講演名 | 2001/1/17 点/枝の線度に基づく最大葉木の近似探索アルゴリズムの考察 森 大祐, 小出 俊夫, 渡部 和, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 情報を多数のユーザに配布する効果的な木状経路を選択する問題は応用範囲が広い.本報告ではその木状経路の1つである最大葉木の近似探索アルゴリズムに関する考察を行う.最大葉木はNP完全問題であり, 一般に単純な木の初等変換による探索方法は実用的ではないが, 葉数増大初等変換の導入によって改善を図った.次に, 点/枝の線度の性質について述べ, 現実に適用可能な時間内で最大葉木を求めるいくつかの近似探索アルゴリズムを提案した.最後に多数の例題に提案したそれぞれのアルゴリズムを適用した結果を比較検討した.その結果, 提案したアルゴリズムの内LDFS木のアルゴリズムが一番効果的に極大葉木を得ることができた事を確かめた. |
| 抄録(英) | This paper proposed and investigated algorithms for finding maximum leaf spanning tree(MLST).Since the tree finding problem is NP complete, simple elementary transformation is not useful.This paper defined leaf increasing elementary transformation and applied it to MLST search.Utilizing newly defined vertex degree and edge degree, several algorithms for finding MLST are also proposed.Investigating many examples of MLST search, it turns out that LDFS-Tree(large-Degree-First-Search-Tree)algorithm is more effective than other proposed algorithms. |
| キーワード(和) | 最大葉木 / グラフ理論 / 初等変換 / 点/枝の線度 / 近似探索アルゴリズム |
| キーワード(英) | Maximum Leaf Spanning Tree / graph theory / elementary transformation / degree of vertex/edge / approximate search algorith |
| 資料番号 | CAS2000-91 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CAS |
|---|---|
| 開催期間 | 2001/1/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Circuits and Systems (CAS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 点/枝の線度に基づく最大葉木の近似探索アルゴリズムの考察 |
| サブタイトル（和） | |
| タイトル（英） | A Consideration of approximate algorithms for finding Maximum Leaf Spanning Tree based on the degree of a vertex/edge |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最大葉木 / Maximum Leaf Spanning Tree |
| キーワード(2)（和/英） | グラフ理論 / graph theory |
| キーワード(3)（和/英） | 初等変換 / elementary transformation |
| キーワード(4)（和/英） | 点/枝の線度 / degree of vertex/edge |
| キーワード(5)（和/英） | 近似探索アルゴリズム / approximate search algorith |
| 第 1 著者 氏名（和/英） | 森 大祐 / Daisuke Mori |
| 第 1 著者 所属（和/英） | 創価大学大学院 工学研究科 Graduate School of Engineering, Soka University |
| 第 2 著者 氏名（和/英） | 小出 俊夫 / Toshio Koide |
| 第 2 著者 所属（和/英） | 創価大学大学院 工学研究科 Graduate School of Engineering, Soka University |
| 第 3 著者 氏名（和/英） | 渡部 和 / Hitoshi Watanabe |
| 第 3 著者 所属（和/英） | 創価大学大学院 工学研究科 Graduate School of Engineering, Soka University |
| 発表年月日 | 2001/1/17 |
| 資料番号 | CAS2000-91 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 573 |
| ページ範囲 | pp.- |
| ページ数 | 4 |
| 発行日 | |