Haidar Harmanani, Jean Hannouche, and Nancy Khoury
Neural networks, combinatorial optimization, graph colouring, FPGAs
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 algo- rithm 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.
Important Links:
Go Back
