A Parallel Neural Networks Algorithm for the Clique Partitioning Problem

LAUR Repository

Show simple item record

dc.contributor.author Harmanani, Haidar M.
dc.date.accessioned 2016-04-12T08:14:05Z
dc.date.available 2016-04-12T08:14:05Z
dc.date.copyright 2002
dc.date.issued 2016-04-12
dc.identifier.issn 1076-5204 en_US
dc.identifier.uri http://hdl.handle.net/10725/3537
dc.description.abstract This paper presents a parallel algorithm to solve the Clique Partitioning Problem, an NP-complete problem. Given a graph G = (V, E), a clique is a complete subgraph in G. The clique partitioning problem is to partition the vertices in G into a number of cliques such that each vertex appears in one and only one clique. The clique partitioning problem has important applications in many areas including VLSI design automation, scheduling, and resources allocation. In this paper we present a parallel algorithm to solve the above problem for arbitrary graphs using a Hopfield Neural Network model of computation. Our model uses a large number of simple processing elements or neurons, based on the McCulloch-Pitts binary neuron. The proposed algorithm has a time complexity of O(1) for a neural network with n vertices and c cliques. A parallel simulator, based on PVM, was implemented for the proposed algorithm on a Linux Cluster. Many graphs were tested, all yielding optimum solutions en_US
dc.language.iso en en_US
dc.title A Parallel Neural Networks Algorithm for the Clique Partitioning Problem en_US
dc.type Article en_US
dc.description.version Published 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 for Computers and Their Applications en_US
dc.journal.volume 9 en_US
dc.journal.issue 2 en_US
dc.article.pages 83-89 en_US
dc.keywords Neural networks en_US
dc.keywords Combinatorial optimization en_US
dc.keywords Clique partitioning en_US
dc.keywords Parallel computing en_US
dc.keywords PVM en_US
dc.identifier.ctation Harmanani, H. M. (2002). A parallel neural networks algorithm for the clique partitioning problem. INTERNATIONAL JOURNAL OF COMPUTERS AND THEIR APPLICATIONS, 9, 83-89. en_US
dc.author.email haidar.harmanani@lau.edu.lb
dc.identifier.url http://s3.amazonaws.com/academia.edu.documents/30978516/

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account