A NEURAL NETWORKS ALGORITHM FOR THE MINIMUM COLOURING PROBLEM USING FPGAs

Haidar Harmanani, Jean Hannouche, and Nancy Khoury

Keywords

Neural networks, combinatorial optimization, graph colouring, 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.

Important Links:



Go Back