Trade-Offs in Custom Circuit Designs for Subgraph Isomorphism Problems

Shuichi ICHIKAWA  Hidemitsu SAITO  Lerdtanaseangtham UDORN  Kouji KONISHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.7   pp.1250-1257
Publication Date: 2003/07/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: VLSI Systems
Keyword: 
NP-complete,  graph,  algorithm,  FPGA,  

Full Text: PDF>>
Buy this Article



Summary: 
Many application programs can be modeled as a subgraph isomorphism problem. However, this problem is generally NP-complete and difficult to compute. A custom computing circuit is a prospective solution for such problems. This paper examines various accelerator designs for subgraph isomorphism problems based on Ullmann's algorithm and Konishi's algorithm. These designs are quantitatively evaluated from two points of view: logic scale and execution time. Our study revealed that Ullmann's design is faster but larger in logic scale. Partially sequential versions of Ullmann's algorithm can be more cost-effective than Ullmann's original design. The hardware of Konishi's algorithm is smaller in logic scale, operates at a higher frequency, and is more cost-effective.