Abstract
A parallel algorithm based on the neural network model for finding a near-maximum clique is presented in this paper. A maximum clique of a graph G is a maximum complete subgraph of G where any two vertices are adjacent. The problem of finding a maximum clique is NP-complete. The parallel algorithm requires n processing elements for an n-vertex graph problem. The algorithm is verified by solving 230 different graph problems. The simulation results show that our computation time on a Macintosh IIfx is shorter than that of two better known algorithms on a Cray 2 and an IBM 3090 while the solution quality is similar. The algorithm solves a near-maximum clique problem in nearly constant time on a parallel machine with n processors.
| Original language | English |
|---|---|
| Pages (from-to) | 340-344 |
| Number of pages | 5 |
| Journal | Journal of Parallel and Distributed Computing |
| Volume | 14 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - Mar 1992 |
| Externally published | Yes |
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence