For Full-Text 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
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/05/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Reconfigurable Computing)
NP-complete, custom circuit, FPGA, graph algorithm,
Full Text: PDF(257.7KB)>>
Although the subgraph isomorphism problem has various important applications, it is generally NP-complete 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.