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