| 講演名 | 2003/1/22 最大クリーク問題を解くインスタンスベースのハードウェア解法とFPGAによる実現 藤原 知幸, 若林 真一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 最大クリーク問題はグラフ理論における基本的問題の一つであるが,大規模かつ複雑な問題をソフトウェアで解くと計算時間が膨大になり,実用時間内で解を得ることができない.本研究では,大規模かつ複雑な最大クリーク問題を対象とし,問題のインスタンスに特化したハードウェアをFPGAを用いて実現することにより最大クリーク問題をハードウェアで解くことを目的とする.与えられた問題のインスタンスをハードウェアで解く場合,インスタンスに特化したハードウェアを短時間で構成可能にすると共に,インスタンスの変更に応じて適宜ハードウェアを再構成することが求められる.そこで,再構成可能なLSIであるFPGAを用いることでインスタンスに特化したハードウェアを実現し,最大クリーク問題を短時間で解く手法を提案し,シミュレーション実験により本手法の有効性を示す. |
| 抄録(英) | The problem of finding a maximum clique is known to be one of fundamental problems in graph theory. But solving the problem by software would not be successful within a practical time if the problem is large and complicatcd. Then we implement instance-specific hardware for a given instance of the maximum clique problem in order to got a solution by hardware. To obtain a solution for a given instance by hardware, we should construct a hardware system dedicated to the specific instance, and make it possible to reconfigure it when another instance is given. For this reason, by using FPGAs that are reconfigurable LSIs, we implement instance-specific hardware and get a solution of the maximum clique problem in a short time. Simulation experiments were performed to show the effectiveness of the proposed method. |
| キーワード(和) | 最大クリーク / 分枝限定法 / インスタンスベース / FPGA |
| キーワード(英) | Maximum Clique / Branch and Bound Algorithm / Instance-Based / FPGAs |
| 資料番号 | VLD20002-138,CPSY2002-91 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2003/1/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 最大クリーク問題を解くインスタンスベースのハードウェア解法とFPGAによる実現 |
| サブタイトル（和） | |
| タイトル（英） | Solving the Maximum Clique Problem Using FPGAs with Instance-Specific Information |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最大クリーク / Maximum Clique |
| キーワード(2)（和/英） | 分枝限定法 / Branch and Bound Algorithm |
| キーワード(3)（和/英） | インスタンスベース / Instance-Based |
| キーワード(4)（和/英） | FPGA / FPGAs |
| 第 1 著者 氏名（和/英） | 藤原 知幸 / Tomoyuki FUJIWARA |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 若林 真一 / Shin'ichi WAKABAYASHI |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2003/1/22 |
| 資料番号 | VLD20002-138,CPSY2002-91 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 609 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |