| 講演抄録／キーワード |
| 講演名 |
2005-01-25 15:20
グラフ最小節点被覆問題に対するFPGAを用いたインスタンス依存ハードウェア解法
○菊池健司・若林真一（広島市大） |
| 抄録 |
（和） |
グラフの最小節点被覆問題を解くインスタンス依存のハードウェア解法を提案し，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 / 最小節点被覆 / インスタンス / 分枝限定 / 論理合成 / / / |
| （英） |
FPGA / minimum vertex cover / instance / branch and bound / logic synthesis / / / |
| 文献情報 |
信学技報, vol. 104, pp. 51-56, 2005年1月. |
| 資料番号 |
|
| 発行日 |
2005-01-18 (VLD, CPSY) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
CPSY VLD IPSJ-SLDM |
| 開催期間 |
2005-01-25 - 2005-01-26 |
| 開催地（和） |
慶應義塾大学 日吉キャンパス |
| 開催地（英） |
|
| テーマ（和） |
FPGAとその応用および一般 |
| テーマ（英） |
FPGA and its Application, etc |
| 講演論文情報の詳細 |
| 申込み研究会 |
IPSJ-SLDM |
| 会議コード |
2005-01-CPSY-VLD-IPSJ-SLDM |
| 本文の言語 |
日本語 |
| タイトル（和） |
グラフ最小節点被覆問題に対するFPGAを用いたインスタンス依存ハードウェア解法 |
| サブタイトル（和） |
|
| タイトル（英） |
An Instance-Specific Hardware Algorithm Using FPGAs for the Mimimum Vertex Cover Problem of a Graph |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
FPGA / FPGA |
| キーワード(2)（和/英） |
最小節点被覆 / minimum vertex cover |
| キーワード(3)（和/英） |
インスタンス / instance |
| キーワード(4)（和/英） |
分枝限定 / branch and bound |
| キーワード(5)（和/英） |
論理合成 / logic synthesis |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
菊池 健司 / Kenji Kikuchi / キクチ ケンジ |
| 第1著者 所属（和/英） |
広島市立大学 (略称： 広島市大)
Hiroshima City University (略称： Hiroshima City Univ.) |
| 第2著者 氏名（和/英/ヨミ） |
若林 真一 / Shin'ichi Wakabayashi / ワカバヤシ シンイチ |
| 第2著者 所属（和/英） |
広島市立大学 (略称： 広島市大)
Hiroshima City University (略称： Hiroshima City Univ.) |
| 第3著者 氏名（和/英/ヨミ） |
/ / |
| 第3著者 所属（和/英） |
(略称： )
(略称： ) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2005-01-25 15:20:00 |
| 発表時間 |
30分 |
| 申込先研究会 |
IPSJ-SLDM |
| 資料番号 |
VLD2004-106, CPSY2004-72 |
| 巻番号（vol） |
vol.104 |
| 号番号（no） |
no.589(VLD), no.591(CPSY) |
| ページ範囲 |
pp.51-56 |
| ページ数 |
6 |
| 発行日 |
2005-01-18 (VLD, CPSY) |
|