Please login using the form on menu list.|
It is required to login for Full-Text PDF.
Trade-Offs in Custom Circuit Designs for Subgraph Isomorphism Problems
IEICE TRANSACTIONS on Information and Systems Vol.E86-D No.7 pp.1250-1257
Publication Date: 2003/07/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: VLSI Systems
Full Text: PDF(328KB)
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.