
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.

TradeOffs in Custom Circuit Designs for Subgraph Isomorphism Problems
Shuichi ICHIKAWA Hidemitsu SAITO Lerdtanaseangtham UDORN Kouji KONISHI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E86D
No.7
pp.12501257 Publication Date: 2003/07/01
Online ISSN: Print ISSN: 09168532 Type of Manuscript: PAPER Category: VLSI Systems Keyword: NPcomplete, graph, algorithm, FPGA,
Full Text: PDF(325.1KB) >>Buy this Article
Summary:
Many application programs can be modeled as a subgraph isomorphism problem. However, this problem is generally NPcomplete 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 costeffective than Ullmann's original design. The hardware of Konishi's algorithm is smaller in logic scale, operates at a higher frequency, and is more costeffective.

