Data Dependent Circuit for Subgraph Isomorphism Problem

Shuichi ICHIKAWA  Shoji YAMAMOTO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.5   pp.796-802
Publication Date: 2003/05/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Reconfigurable Computing)
Category: 
Keyword: 
NP-complete,  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 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.