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!
|
| _version_ | 1864513461383331840 |
|---|---|
| author | Harmanani, Haidar |
| author2 | Hannouche, Jean Khoury, Nancy |
| author2_role | author author |
| author_facet | Harmanani, Haidar Hannouche, Jean Khoury, Nancy |
| author_role | author |
| dc.creator.none.fl_str_mv | Harmanani, Haidar Hannouche, Jean Khoury, Nancy |
| dc.date.none.fl_str_mv | 2010 2016-04-12T07:57:14Z 2016-04-12T07:57:14Z 2016-04-12 |
| dc.identifier.none.fl_str_mv | 0228-6203 http://hdl.handle.net/10725/3536 http://dx.doi.org/10.1080/02286203.2010.11442597 Harmanani, H., Hannouche, J., & Khoury, N. (2010). A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs†. International Journal of Modelling and Simulation, 30(4), 506-513. http://www.tandfonline.com/doi/abs/10.1080/02286203.2010.11442597 |
| dc.relation.none.fl_str_mv | International Journal of Modelling and Simulation |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs† |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_6ea010e499cb988c095df50e71b75331 |
| identifier_str_mv | 0228-6203 Harmanani, H., Hannouche, J., & Khoury, N. (2010). A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs†. International Journal of Modelling and Simulation, 30(4), 506-513. |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/3536 |
| publishDate | 2010 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs†Harmanani, HaidarHannouche, JeanKhoury, NancyThis 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.N/AN/A2016-04-12T07:57:14Z2016-04-12T07:57:14Z20102016-04-12Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article0228-6203http://hdl.handle.net/10725/3536http://dx.doi.org/10.1080/02286203.2010.11442597Harmanani, H., Hannouche, J., & Khoury, N. (2010). A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs†. International Journal of Modelling and Simulation, 30(4), 506-513.http://www.tandfonline.com/doi/abs/10.1080/02286203.2010.11442597International Journal of Modelling and Simulationinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/35362016-08-11T08:30:58Z |
| spellingShingle | A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs† Harmanani, Haidar |
| status_str | publishedVersion |
| title | A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs† |
| title_full | A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs† |
| title_fullStr | A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs† |
| title_full_unstemmed | A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs† |
| title_short | A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs† |
| title_sort | A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs† |
| url | 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 |