A Hardware Algorithm for the Minimum p-quasi Clique Cover Problem
Shuichi Watanabe, Junji Kitamichi, Kenichi Kuroda · 2007
In this paper, we describe a hardware algorithm for the minimum p-quasi clique cover (MPQCC) problem and its implementation on an FPGA. MPQCC problem is a combinational optimization problem that is NP-complete. Furthermore, gene expression profile analysis is one of applied fields of MPQCC problem. We aim to develop an inexpensive acceleration system using FPGAs for gene expression profile analysis. We adopt a Hopfield neural network for the proposed algorithm for the reduction of the calculation time. The proposed architecture using a ring network can execute the proposed algorithm effectively on FPGAs because each module can run in parallel independently and the system can be implemented with simple placement and routing of modules, and high scalability. We show that the proposed method is better than the existing one with regard to its solution searching ability and required calculation time.