| Presentation | 2012-11-28 A Hardware Algorithm Using Dynamically Partially Reconfigurable FPGA for Solving the Maximum Clique Problem of Large Graphs Chikako MIURA, Shinobu NAGAYAMA, Shin'ichi WAKABAYASHI, Masato INAGI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we propose a hardware algorithm to solve the maximum clique problem of large graphs, and show its implementation results using a dynamically partially reconfigurable FPGA. Although existing hardware algorithms cannot solve the problem for graphs with many nodes due to the resource limitation on an FPGA, the proposed algorithm can solve the problem for such large graphs using only one FPGA by generating subgraphs from a given graph, and implementing them using dynamically partial reconfiguration of an FPGA. Since the proposed hardware algorithm is based on a branch-and-bound method, it can explore solution space efficiently, and reduce the number of partial reconfigurations of FPGA. Our experimental results using a dynamically partially reconfigurable FPGA show that the proposed algorithm can efficiently solve the problem that an existing algorithm cannot solve. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | maximum clique problem / branch-and-bound method / FPGA / partial reconfiguration |
| Paper # | RECONF2012-53 |
| Date of Issue |
| Conference Information | |
| Committee | RECONF |
|---|---|
| Conference Date | 2012/11/20(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Reconfigurable Systems (RECONF) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Hardware Algorithm Using Dynamically Partially Reconfigurable FPGA for Solving the Maximum Clique Problem of Large Graphs |
| Sub Title (in English) | |
| Keyword(1) | maximum clique problem |
| Keyword(2) | branch-and-bound method |
| Keyword(3) | FPGA |
| Keyword(4) | partial reconfiguration |
| 1st Author's Name | Chikako MIURA |
| 1st Author's Affiliation | Graduate School of Information Sciences, Hiroshima City University() |
| 2nd Author's Name | Shinobu NAGAYAMA |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Hiroshima City University |
| 3rd Author's Name | Shin'ichi WAKABAYASHI |
| 3rd Author's Affiliation | Graduate School of Information Sciences, Hiroshima City University |
| 4th Author's Name | Masato INAGI |
| 4th Author's Affiliation | Graduate School of Information Sciences, Hiroshima City University |
| Date | 2012-11-28 |
| Paper # | RECONF2012-53 |
| Volume (vol) | vol.112 |
| Number (no) | 325 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |