A neural network model for finding a near-maximum clique

✍ Scribed by Nubuo Funabiki; Yoshiyasu Takefuji; Kuo-Chun Lee

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 397 KB
• Volume: 14
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1016/0743-7315(92)90072-u

✦ Synopsis

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. o 1%~ Academic Press, Inc.