H. Harmanani, J. Hannouche, and N. Khoury (Lebanon)
Neural Networks, Combinatorial Optimization, graph coloring, FPGAs.
This paper presents a hardware implementation to solve the graph coloring problem (chromatic number χ(G)) for arbitrary graphs using the hopfield neural network model of computation. The graph coloring 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 colors. The algorithm was implemented using VHDL and downloaded on a Field Programmable Gate Array (FPGA) device. The algorithm was simulated and tested on various graphs, all yielding optimum solutions.
Important Links:
Go Back
