| 講演名 | 2005-01-25 グラフ最小節点被覆問題に対するFPGAを用いたインスタンス依存ハードウェア解法(応用1, FRGAとその応用及び一般) 菊池 健司, 若林 真一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフの最小節点被覆問題を解くインスタンス依存のハードウェア解法を提案し, FPGA上に実現して, その性能をソフトウェアによる解法と比較した.提案ハードウェア解法は分枝限定法に基づいており, 入力グラフのインスタンスに依存したハードウェア構成の回路記述を自動的に生成し, 論理合成, 配置配線を行った上で回路データをFPGA上にダウンロードして実行する.ソフトウェアによる解法と比較した結果, 回路生成時間を考慮しても提案手法はソフトウェアより短い計算時間で解を得ることが分かった. |
| 抄録(英) | This report presents a hardware algorithm for finding a minimum vertex cover of a given graph, and shows experimental evaluation of the proposed algorithm on an FPGA. The proposed algorithm is constructed according to a given instance of graph, and can find a minimum vertex cover efficiently based on branch and bound search. The proposed algorithm is supposed to be implemented with hardware, and realizes an efficient branch and bound search with parallel and pipeline processing. The proposed algorithm was implemented on an FPGA, and its running time was measured. Compared with the solving method with software, the proposed algorithm found a minimum vertex cover in a shorter running time. |
| キーワード(和) | 最小節点被覆 / インスタンス / 分枝限定 / 論理合成 |
| キーワード(英) | FPGA / minimum vertex cover / instance / branch and bound / logic synthesis |
| 資料番号 | VLD2004-106,CPSY2004-72 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2005/1/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グラフ最小節点被覆問題に対するFPGAを用いたインスタンス依存ハードウェア解法(応用1, FRGAとその応用及び一般) |
| サブタイトル（和） | |
| タイトル（英） | An Instance-Specific Hardware Algorithm Using FPGAs for the Mimimum Vertex Cover Problem of a Graph |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最小節点被覆 / FPGA |
| キーワード(2)（和/英） | インスタンス / minimum vertex cover |
| キーワード(3)（和/英） | 分枝限定 / instance |
| キーワード(4)（和/英） | 論理合成 / branch and bound |
| 第 1 著者 氏名（和/英） | 菊池 健司 / Kenji KIKUCHI |
| 第 1 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 第 2 著者 氏名（和/英） | 若林 真一 / Shinichi WAKABAYASHI |
| 第 2 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 発表年月日 | 2005-01-25 |
| 資料番号 | VLD2004-106,CPSY2004-72 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 589 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |