Bioinspired Parallel Algorithms for Maximum Clique Problem on FPGA Architectures

摘要

The stickers model is a model of DNA computation that is computationally complete and universal. Many NP complete problems can be described by stickers programs that have polynomial runtime and are exponential in space. The stickers model can be viewed as a bit-vertically operating register machine. This makes it attractive for in silico implementation. This paper describes a stickers model for the maximum clique problem and its implementation by an FPGA architecture. The results show that the FPGA based algorithm is comparable with existing software algorithms for moderate problem sizes. More generally, the stickers model seems to be a well-suited programming model for dedicated hardware. Keywords DNA computing - Stickers model - Maximum clique problem - FPGA