A Neural Networks Algorithm for the Minimum Colouring Problem Using 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 tabli...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | article |
| Published: |
2010
|
| Online Access: | http://hdl.handle.net/10725/3536 http://dx.doi.org/10.1080/02286203.2010.11442597 http://www.tandfonline.com/doi/abs/10.1080/02286203.2010.11442597 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|