Research work · 2002

Hardware accelerator for subgraph isomorphism problems

Shûichi Ichikawa, Lerdtanaseangtham Udorn, K. Konishi

IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM)

Abstract

Many applications can be modeled as subgraph isomorphism problems, which are generally NP-complete. This paper presents an algorithm that is suited for hardware implementation. The prototype accelerator that operates at 16.5 MHz on a Lucent ORCA 2C15A FPGA outperforms the software implementation of Ullmann's algorithm on a 400 MHz Pentium II by 10 times in the best case.

DOI: 10.1109/fpga.2000.903417