| Presentation | 2014-01-28 A Unified Software/Reconfigurable Hardware Approach to 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) | We propose an algorithm to solve the maximum clique problem of large graphs. The proposed algorithm is a unified software/reconfigurable hardware approach based on a branch-and-bound method. It consists of a software part for generating subgraphs from given graphs, and a hardware part for efficiently exploring solutions of subgraphs. This paper shows implementation results of the hardware part on FPGA. The proposed algorithm can efficiently solve the problem by branch-and-bound method to generate subgraphs, reduce the design time of logical synthesis etc., and solve the problem in a short time even when exploring solutions of many subgraphs by implementing an instance independent circuit of the problem on FPGA. Our experimental results showed that the proposed algorithm can efficiently solve a problem instance that an existing algorithm could not solve. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | maximum clique problem / branch-and-bound method / FPGA / instance |
| Paper # | VLD2013-103,CPSY2013-74,RECONF2013-57 |
| Date of Issue |
| Conference Information | |
| Committee | RECONF |
|---|---|
| Conference Date | 2014/1/21(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 Unified Software/Reconfigurable Hardware Approach to 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) | instance |
| 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 | / / |
| 3rd Author's Name | Shin'ichi WAKABAYASHI |
| 3rd Author's Affiliation | |
| 4th Author's Name | Masato INAGI |
| 4th Author's Affiliation | |
| Date | 2014-01-28 |
| Paper # | VLD2013-103,CPSY2013-74,RECONF2013-57 |
| Volume (vol) | vol.113 |
| Number (no) | 418 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |