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.
Trade-Offs in Custom Circuit Designs for Subgraph Isomorphism Problems
Shuichi ICHIKAWA Hidemitsu SAITO Lerdtanaseangtham UDORN Kouji KONISHI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/07/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: VLSI Systems
NP-complete, graph, algorithm, FPGA,
Full Text: PDF(325.1KB)>>
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.