
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Data Dependent Circuit for Subgraph Isomorphism Problem
Shuichi ICHIKAWA Shoji YAMAMOTO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E86D
No.5
pp.796802 Publication Date: 2003/05/01
Online ISSN: Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Issue on Reconfigurable Computing) Category: Keyword: NPcomplete, custom circuit, FPGA, graph algorithm,
Full Text: PDF(257.7KB) >>Buy this Article
Summary:
Although the subgraph isomorphism problem has various important applications, it is generally NPcomplete and difficult to solve. Though a custom computing circuit can reduce the execution time substantially, it requires considerable hardware resources and is inapplicable to large problems. This paper examines the feasibility of data dependent designs, which are particularly suitable to a Field Programmable Gate Array (FPGA). The data dependent approach drastically reduces hardware requirements. For graphs of 32 vertices, the average logic scale of data dependent circuits is only 5% of the corresponding data independent circuit. The data dependent circuit is estimated to be maximally 460 times faster than the software. Even if the circuit generation time is included, a data dependent circuit is estimated to be 2.04 times faster than software for graphs of 32 vertices. The performance gain would increase for larger graphs.

