A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs†

LAUR Repository

Show simple item record

dc.contributor.author Harmanani, Haidar
dc.contributor.author Hannouche, Jean
dc.contributor.author Khoury, Nancy
dc.date.accessioned 2016-04-12T07:57:14Z
dc.date.available 2016-04-12T07:57:14Z
dc.date.copyright 2010
dc.date.issued 2016-04-12
dc.identifier.issn 0228-6203 en_US
dc.identifier.uri http://hdl.handle.net/10725/3536
dc.description.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. en_US
dc.title A Neural Networks Algorithm for the Minimum Colouring Problem Using FPGAs† en_US
dc.type Article en_US
dc.description.version N/A en_US
dc.author.school SAS en_US
dc.author.idnumber 199490170 en_US
dc.author.woa N/A en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal International Journal of Modelling and Simulation en_US
dc.journal.volume 30 en_US
dc.journal.issue 4 en_US
dc.article.pages 506-513 en_US
dc.keywords Neural networks en_US
dc.keywords Combinatorial optimization en_US
dc.keywords Graph colouring en_US
dc.keywords FPGAs en_US
dc.identifier.doi http://dx.doi.org/10.1080/02286203.2010.11442597 en_US
dc.identifier.ctation 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. en_US
dc.author.email haidar.harmanani@lau.edu.lb
dc.identifier.url http://www.tandfonline.com/doi/abs/10.1080/02286203.2010.11442597

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account