A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs†

Abstract

This paper presents a hardware implementation to solve the graph colouring problem (chromatic number χ(G)) for arbitrary graphs using the Hopfield neural network (HNN) model of computation. The graph colouring problem, an NP-hard problem, has important applications in many areas including time tabling and scheduling, frequency assignment, and register allocation. The proposed algorithm has a time complexity of O(1) for a neural network with n vertices and k colours. The algorithm was implemented using VHSIC hardware description language (VHDL) and downloaded on a field programmable gate array (FPGA) device. The resulting hardware was simulated and tested on various graphs, all yielding optimum solutions.