A Parallel Neural Networks Algorithm for the Clique Partitioning Problem
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 a...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | article |
| منشور في: |
2002
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/3537 http://s3.amazonaws.com/academia.edu.documents/30978516/10.1.1.3.258.pdf?AWSAccessKeyId=AKIAJ56TQJRTWSMTNPEA&Expires=1470914575&Signature=bMI6N%2FJHnxDvhq%2F%2Fh9iThifeZRM%3D&response-content-disposition=inline%3B%20filename%3DA_parallel_neural_networks_algorithm_for.pdf |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513461384380416 |
|---|---|
| author | Harmanani, Haidar M. |
| author_facet | Harmanani, Haidar M. |
| author_role | author |
| dc.creator.none.fl_str_mv | Harmanani, Haidar M. |
| dc.date.none.fl_str_mv | 2002 2016-04-12T08:14:05Z 2016-04-12T08:14:05Z 2016-04-12 |
| dc.identifier.none.fl_str_mv | 1076-5204 http://hdl.handle.net/10725/3537 Harmanani, H. M. (2002). A parallel neural networks algorithm for the clique partitioning problem. INTERNATIONAL JOURNAL OF COMPUTERS AND THEIR APPLICATIONS, 9, 83-89. http://s3.amazonaws.com/academia.edu.documents/30978516/10.1.1.3.258.pdf?AWSAccessKeyId=AKIAJ56TQJRTWSMTNPEA&Expires=1470914575&Signature=bMI6N%2FJHnxDvhq%2F%2Fh9iThifeZRM%3D&response-content-disposition=inline%3B%20filename%3DA_parallel_neural_networks_algorithm_for.pdf |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | International Journal for Computers and Their Applications |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | A Parallel Neural Networks Algorithm for the Clique Partitioning Problem |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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 |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_dd4000cbdbc03ed639dd4e2a67239497 |
| identifier_str_mv | 1076-5204 Harmanani, H. M. (2002). A parallel neural networks algorithm for the clique partitioning problem. INTERNATIONAL JOURNAL OF COMPUTERS AND THEIR APPLICATIONS, 9, 83-89. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/3537 |
| publishDate | 2002 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | A Parallel Neural Networks Algorithm for the Clique Partitioning ProblemHarmanani, Haidar M.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 solutionsPublishedN/A2016-04-12T08:14:05Z2016-04-12T08:14:05Z20022016-04-12Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article1076-5204http://hdl.handle.net/10725/3537Harmanani, H. M. (2002). A parallel neural networks algorithm for the clique partitioning problem. INTERNATIONAL JOURNAL OF COMPUTERS AND THEIR APPLICATIONS, 9, 83-89.http://s3.amazonaws.com/academia.edu.documents/30978516/10.1.1.3.258.pdf?AWSAccessKeyId=AKIAJ56TQJRTWSMTNPEA&Expires=1470914575&Signature=bMI6N%2FJHnxDvhq%2F%2Fh9iThifeZRM%3D&response-content-disposition=inline%3B%20filename%3DA_parallel_neural_networks_algorithm_for.pdfenInternational Journal for Computers and Their Applicationsinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/35372016-08-11T10:23:43Z |
| spellingShingle | A Parallel Neural Networks Algorithm for the Clique Partitioning Problem Harmanani, Haidar M. |
| status_str | publishedVersion |
| title | A Parallel Neural Networks Algorithm for the Clique Partitioning Problem |
| title_full | A Parallel Neural Networks Algorithm for the Clique Partitioning Problem |
| title_fullStr | A Parallel Neural Networks Algorithm for the Clique Partitioning Problem |
| title_full_unstemmed | A Parallel Neural Networks Algorithm for the Clique Partitioning Problem |
| title_short | A Parallel Neural Networks Algorithm for the Clique Partitioning Problem |
| title_sort | A Parallel Neural Networks Algorithm for the Clique Partitioning Problem |
| url | http://hdl.handle.net/10725/3537 http://s3.amazonaws.com/academia.edu.documents/30978516/10.1.1.3.258.pdf?AWSAccessKeyId=AKIAJ56TQJRTWSMTNPEA&Expires=1470914575&Signature=bMI6N%2FJHnxDvhq%2F%2Fh9iThifeZRM%3D&response-content-disposition=inline%3B%20filename%3DA_parallel_neural_networks_algorithm_for.pdf |