抄録
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.
| 本文言語 | English |
|---|---|
| ページ（範囲） | 340-344 |
| ページ数 | 5 |
| ジャーナル | Journal of Parallel and Distributed Computing |
| 巻 | 14 |
| 号 | 3 |
| DOI | |
| 出版ステータス | Published - 3月 1992 |
| 外部発表 | はい |
ASJC Scopus subject areas
- ソフトウェア
- 理論的コンピュータサイエンス
- ハードウェアとアーキテクチャ
- コンピュータ ネットワークおよび通信
- 人工知能