Paper Abstract and Keywords |
Presentation |
2014-01-28 08:55
A Unified Software/Reconfigurable Hardware Approach to Solving the Maximum Clique Problem of Large Graphs Chikako Miura, Shinobu Nagayama, Shin'ichi Wakabayashi, Masato Inagi (Hiroshima City Univ.) VLD2013-103 CPSY2013-74 RECONF2013-57 |
Abstract |
(in Japanese) |
(See Japanese page) |
(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) |
(in English) |
maximum clique problem / branch-and-bound method / FPGA / instance / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 113, no. 418, RECONF2013-57, pp. 7-12, Jan. 2014. |
Paper # |
RECONF2013-57 |
Date of Issue |
2014-01-21 (VLD, CPSY, RECONF) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
VLD2013-103 CPSY2013-74 RECONF2013-57 |
Conference Information |
Committee |
IPSJ-SLDM CPSY RECONF VLD |
Conference Date |
2014-01-28 - 2014-01-29 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Hiyoshi Campus, Keio University |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
FPGA Applications, etc |
Paper Information |
Registration To |
RECONF |
Conference Code |
2014-01-SLDM-CPSY-RECONF-VLD |
Language |
Japanese |
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 |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Chikako Miura |
1st Author's Affiliation |
Hiroshima City University (Hiroshima City Univ.) |
2nd Author's Name |
Shinobu Nagayama |
2nd Author's Affiliation |
Hiroshima City University (Hiroshima City Univ.) |
3rd Author's Name |
Shin'ichi Wakabayashi |
3rd Author's Affiliation |
Hiroshima City University (Hiroshima City Univ.) |
4th Author's Name |
Masato Inagi |
4th Author's Affiliation |
Hiroshima City University (Hiroshima City Univ.) |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2014-01-28 08:55:00 |
Presentation Time |
25 minutes |
Registration for |
RECONF |
Paper # |
VLD2013-103, CPSY2013-74, RECONF2013-57 |
Volume (vol) |
vol.113 |
Number (no) |
no.416(VLD), no.417(CPSY), no.418(RECONF) |
Page |
pp.7-12 |
#Pages |
6 |
Date of Issue |
2014-01-21 (VLD, CPSY, RECONF) |
|