| Presentation | 2004/1/16 Implementation and Evaluation of an Instance-Specific Hardware Algorithm for Finding a Maximum Clique Shin'ichi WAKABAYASHI, Kenji KIKUCHI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This report presents a hardware algorithm for finding a maximum clique of a given graph, and shows experimental evaluation of implementation of the proposed algorithm on an FPGA. The proposed algorithm is constructed according to a. given instance of graph, and can find a maximum clique efficiently based on branch and bound search. The proposed algorithm is supposed to be implmented 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 produced a maximum clique in a shorter running time. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | FPGA / maximum clique / instance / branch and bound / logic synthesis |
| Paper # | VLD2003-135,CPSY2003-44 |
| Date of Issue |
| Conference Information | |
| Committee | VLD |
|---|---|
| Conference Date | 2004/1/16(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 | VLSI Design Technologies (VLD) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Implementation and Evaluation of an Instance-Specific Hardware Algorithm for Finding a Maximum Clique |
| Sub Title (in English) | |
| Keyword(1) | FPGA |
| Keyword(2) | maximum clique |
| Keyword(3) | instance |
| Keyword(4) | branch and bound |
| Keyword(5) | logic synthesis |
| 1st Author's Name | Shin'ichi WAKABAYASHI |
| 1st Author's Affiliation | Faculty of Information Sciences, Hiroshima City University() |
| 2nd Author's Name | Kenji KIKUCHI |
| 2nd Author's Affiliation | Faculty of Information Sciences, Hiroshima City University |
| Date | 2004/1/16 |
| Paper # | VLD2003-135,CPSY2003-44 |
| Volume (vol) | vol.103 |
| Number (no) | 579 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |