| 講演名 | 2004/1/16 反転禁止部分グラフを含む平面グラフ抽出法の効率化(FPGAとその応用及び一般) 木下 敏行, 高藤 大介, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 反転禁止部分グラフを有する平面グラフを抽出する発見的解法は現在までにいくつか提案されているが,数万頂点という実用規模のグラフモデルに対しては計算時間・使用メモリ量の面で実用に供する手法は未提案である.本稿では,このような規模のグラフモデルに対して上記問題を実用的計算時間内で解くことができる並列解法を3つ提案し,これらと既存の4つの直列解法の性能を計算機実験により比較評価する. |
| 抄録(英) | Although several algorithms for extraction of a planar graph with subgraphs whose turning over is forbidden has been proposed, it does not seem that there exists any algorithm that can be used for large graphs appearing in practical situation. In this paper we propose three parallel algorithms that extract such planar subgraphs in realistic computation time. Performance of these three algorithms as well as four existing sequential algorithms is evaluated through experimental results. |
| キーワード(和) | 平面グラフ抽出 / 反転禁止 / 並列アルゴリズム / 計算時間 |
| キーワード(英) | Planar graph extraction / turn-forbiddance / parallel algorithms / computation time |
| 資料番号 | VLD2003-125,CPSY2003-34 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2004/1/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 反転禁止部分グラフを含む平面グラフ抽出法の効率化(FPGAとその応用及び一般) |
| サブタイトル（和） | |
| タイトル（英） | Efficient Extraction of a Planar Graph with Subgraphs whose Turning Over is Forbidden |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 平面グラフ抽出 / Planar graph extraction |
| キーワード(2)（和/英） | 反転禁止 / turn-forbiddance |
| キーワード(3)（和/英） | 並列アルゴリズム / parallel algorithms |
| キーワード(4)（和/英） | 計算時間 / computation time |
| 第 1 著者 氏名（和/英） | 木下 敏行 / Toshiyuki KINOSHITA |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 高藤 大介 / Daisuke TAKAFUJI |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 3 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2004/1/16 |
| 資料番号 | VLD2003-125,CPSY2003-34 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 579 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |