A Parallel Neural Networks Algorithm for the Clique Partitioning Problem

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