Hardware Accelerator for Subgraph Isomorphism Problems

Author: S. Ichikawa, L. Udorn, and K. Konishi

Proceedings of the Eighth IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'00), pp. 283--284 (2000).


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.